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 - Г.Агапова и И.Фефера