Ұялы байланыс компаниясы келесі акцияны ұсынады: әрбір жаңа клиент дәл $k$ басқа телефон нөмірін таңдай алады және клиент пен таңдалған $k$ контактінің кез келгені арасындағы барлық қоңыраулар (екі бағытта да) тегін болады.
$n$ студенттен тұратын топ ($1$-ден $n$-ге дейін нөмірленген) осы акцияны пайдаланғысы келеді. Әрбір $i$ студенті $\{1, 2, \dots, n\} \setminus \{i\}$ жиынынан дәл $k$ әртүрлі контактіні таңдауы тиіс.
Егер келесі шарттардың кем дегенде біреуі орындалса, екі студент $i$ мен $j$ тегін сөйлесе алады деп айтамыз:
- $i$ тегін контактілердің бірі ретінде $j$-ді таңдаған, немесе
- $j$ тегін контактілердің бірі ретінде $i$-ді таңдаған.
Студенттер кез келген студент кез келген басқа студентпен тегін сөйлесе алатындай етіп, яғни $1 \le i < j \le n$ болатын әрбір $(i, j)$ жұбы үшін $i$ мен $j$ студенттері тегін сөйлесе алатындай етіп өздерінің тегін контактілерін таңдағысы келеді.
Берілген $k$ үшін сіздің міндетіңіз:
- осындай конфигурация мүмкін болатын студенттердің ең көп мүмкін саны $n$-ді анықтау,
- осы максималды $n$ үшін таңдалған контактілердің бір дұрыс конфигурациясын құрастыру.
Кіріс деректер
Кіріс деректер бір бүтін саннан $k$ тұрады.
Шығыс деректер
Бірінші жолда бір бүтін санды $n$ — кез келген екі студент бір-бірімен тегін сөйлесе алатындай етіп тегін контактілерді таңдауға болатын студенттердің максималды санын шығарыңыз.
Келесі $n$ жолда әр студент таңдаған $k$ тегін контактіні шығарыңыз: $i+1$ жолында ($1 \le i \le n$ үшін) $k$ әртүрлі бүтін сандарды $a_{i,1}, a_{i,2}, \dots, a_{i,k}$ шығарыңыз. Әрбір $a_{i,j}$ мәні $1 \le a_{i,j} \le n$ және $a_{i,j} \neq i$ шарттарын қанағаттандыруы керек. Бұл жолдар $i$ студенті өзінің тегін контактілері ретінде $a_{i,1}, a_{i,2}, \dots, a_{i,k}$ студенттерін таңдағанын білдіреді.
Егер бірнеше дұрыс жауап болса, олардың кез келгенін шығарыңыз.
Шектеулер
- $1 \le k \le 1000$.
Мысал 1
2
5
2 5
3 4
1 5
1 3
2 4
Ескертпелер
Мысалда $k = 2$, ал кез келген екі студент бір-бірімен тегін сөйлесе алатындай етіп тегін контактілерді таңдауға болатын студенттердің максималды саны $n = 5$. Әртүрлі студенттердің әрбір жұбы үшін олардың кем дегенде біреуі екіншісін таңдаған, сондықтан кез келген екеуі тегін сөйлесе алады.