В данной задаче от Вас требуется построить граф-турнир, состоящий из n вершин, такой, что для любой ориентированной пары вершин (v, u)(v ≠ u) существует путь из вершины v в вершину u длины не более двух ребер.
Ориентированный граф без петель называется турниром, если между любыми его двумя различными вершинами есть ровно одно ребро (в одном из двух возможных направлений).
Выходные данные
Выведите -1, если не существует ни одного графа, удовлетворяющего описанным условиям.
Иначе выведите n строк, в каждой строке по n целых чисел, разделенных пробелами, — матрицу смежности a найденного турнира. Считайте, что вершины графа пронумерованы целыми числами от 1 до n. Тогда av, u = 0, если в турнире нет ребра из вершины v в вершину u, и av, u = 1, если ребро есть.
Так как выведенный граф должен быть турниром, то должны выполняться следующие равенства:
- av, u + au, v = 1 для всех v, u (1 ≤ v, u ≤ n; v ≠ u);
- av, v = 0 для всех v (1 ≤ v ≤ n).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
|
0 1 0
0 0 1
1 0 0
|
|
2
|
4
|
-1
|