eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Граф-турнір

Граф-турнір

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

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

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

Вхідні дані

У першому рядку записано єдине ціле число n (3n1000) — кількість вершин графа.

Вихідні дані

Виведіть -1, якщо не існує жодного графа, який задовольняє описаним умовам.

Інакше виведіть n рядків, у кожному рядку по n чисел, відокремлених пропусками, — матрицю суміжності a знайденого турніру. Вважайте, що вершини графа пронумеровано цілими числами від 1 до n. Тоді a_{v,u} = 0, якщо в турнірі немає ребра з вершини v у вершину u, і a_{v,u} = 1, якщо ребро є.

Так як виведений граф повинен бути турніром, то повинні виконуватись наступні рівності:

  • a_{v,u} + a_{u,v} = 1 для усіх v, u (1v, un, vu);

  • a_{v,v} = 0 для усіх v (1vn).

Приклад

Вхідні дані #1
3
Вихідні дані #1
0 1 0
0 0 1
1 0 0
Джерело Зимова школа Харків 2013, День 6 - Г.Агапова та І.Фефера