e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Граф-турнир

Граф-турнир

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

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

Входные данные

В первой строке записано единственное целое число n (3n1000) — количество вершин графа.

Выходные данные

Выведите -1, если не существует ни одного графа, удовлетворяющего описанным условиям.

Иначе выведите n строк, в каждой строке по n чисел, разделенных пробелами, — матрицу смежности a найденного турнира. Считайте, что вершины графа пронумерованы целыми числами от 1 до n. Тогда av,u = 0, если в турнире нет ребра из вершины v в вершину u, и av,u = 1, если ребро есть.

Так как выведенный граф должен быть турниром, то должны выполняться следующие равенства:

  • av,u + au,v = 1 для всех v, u (1v, un, vu);
  • av,v = 0 для всех v (1vn).
Time limit 1 second
Memory limit 256 MiB
Input example #1
3
Output example #1
0 1 0
0 0 1
1 0 0
Source Winter School Kharkov 2013, Day 6 - G.Agapov and I.Fefer