Телефонна компанія#13012

Телефонна компанія

2 секунди
512 мегабайтів
Середня

Мобільний оператор пропонує таку акцію: кожен новий абонент може вибрати рівно інших телефонних номерів, і всі дзвінки між ним та будь-яким із цих контактів будуть безкоштовними (в обох напрямках).

Група з студентів (пронумерованих від до ) хоче скористатися цією акцією. Кожен студент повинен вибрати рівно різних контактів із множини \{1,2,\dots,n\} \setminus \{i\}.

Вважатимемо, що два студенти та можуть безкоштовно спілкуватися, якщо виконується хоча б одна з таких умов:

Студенти хочуть вибрати свої безкоштовні контакти так, щоб будь-які двоє студентів могли безкоштовно спілкуватися між собою, тобто для кожної пари , де 1 \le i < j \le n, студенти та могли телефонувати один одному безкоштовно.

Для заданого необхідно:

Вхідні дані

У першому рядку задано ціле число .

1 \le k \le 1000.

Вихідні дані

У першому рядку виведіть одне ціле число — максимальну кількість студентів, для якої можна вибрати безкоштовні контакти так, щоб будь-які двоє студентів могли безкоштовно спілкуватися.

У наступних рядках виведіть по безкоштовних контактів, вибраних кожним студентом: у рядку i+1 (для 1 \le i \le n) виведіть різних цілих чисел a_{i,1}, a_{i,2}, \dots, a_{i,k}. Кожне число a_{i,j} повинно задовольняти умови 1 \le a_{i,j} \le n та a_{i,j} \ne i. Ці рядки означають, що студент вибрав студентів a_{i,1}, a_{i,2}, \dots, a_{i,k} як свої безкоштовні контакти.

Якщо існує декілька правильних відповідей, виведіть будь-яку з них.

Приклади

Приклад

Loading
Loading

Примітка

У прикладі k = 2, а максимальна кількість студентів, для якої можна вибрати безкоштовні контакти так, щоб будь-які двоє студентів могли безкоштовно спілкуватися, дорівнює n = 5.

Для кожної пари різних студентів принаймні один із них вибрав іншого як безкоштовний контакт, тому будь-які двоє студентів можуть безкоштовно телефонувати один одному.