Farsímafyrirtæki býður upp á eftirfarandi tilboð: hver nýr viðskiptavinur má velja nákvæmlega $k$ önnur símanúmer og öll símtöl milli viðskiptavinarins og hvaða sem er af þessum $k$ völdu tengiliðum eru ókeypis (í báðar áttir).
Hópur $n$ nemenda (númeraðir frá $1$ til $n$) vill nýta sér þetta tilboð. Hver nemandi $i$ verður að velja nákvæmlega $k$ ólíka tengiliði úr menginu $\{1, 2, \dots, n\} \setminus \{i\}$.
Við segjum að tveir nemendur $i$ og $j$ geti talað saman ókeypis ef að minnsta kosti annað af eftirfarandi gildir:
- $i$ hefur valið $j$ sem einn af ókeypis tengiliðunum, eða
- $j$ hefur valið $i$ sem einn af ókeypis tengiliðunum.
Nemendurnir vilja velja ókeypis tengiliði sína þannig að sérhver nemandi geti talað við hvaða annan nemanda sem er ókeypis, þ.e. fyrir sérhvert par $(i, j)$ með $1 \le i < j \le n$ geta nemendur $i$ og $j$ talað saman ókeypis.
Fyrir gefið $k$ er verkefni þitt að:
- ákvarða mesta mögulega fjölda $n$ nemenda sem slík uppsetning er möguleg fyrir,
- smíða eina gilda uppsetningu á völdum tengiliðum fyrir þetta hámarks $n$.
Inntak
Inntakið samanstendur af einni heiltölu $k$.
Úttak
Á fyrstu línuna skal prenta eina heiltölu $n$ — hámarksfjölda nemenda sem hægt er að velja ókeypis tengiliði fyrir þannig að hvaða tveir nemendur sem er geti talað saman ókeypis.
Á næstu $n$ línur skal prenta þá $k$ ókeypis tengiliði sem hver nemandi velur: á línu $i+1$ (fyrir $1 \le i \le n$), prentið $k$ ólíkar heiltölur $a_{i,1}, a_{i,2}, \dots, a_{i,k}$. Hvert $a_{i,j}$ verður að uppfylla $1 \le a_{i,j} \le n$ og $a_{i,j} \neq i$. Þessar línur gefa til kynna að nemandi $i$ hafi valið nemendurna $a_{i,1}, a_{i,2}, \dots, a_{i,k}$ sem ókeypis tengiliði sína.
Ef það eru fleiri en eitt gilt svar má prenta hvaða sem er þeirra.
Takmarkanir
- $1 \le k \le 1000$.
Dæmi 1
2
5
2 5
3 4
1 5
1 3
2 4
Athugasemdir
Í dæminu er $k = 2$ og hámarksfjöldi nemenda þar sem hægt er að velja ókeypis tengiliði þannig að hvaða tveir nemendur sem er geti talað saman ókeypis er $n = 5$. Fyrir hvert par ólíkra nemenda hefur að minnsta kosti annar þeirra valið hinn, svo hvaða tveir sem er geta talað saman ókeypis.