eolymp
bolt
Try our new interface for solving problems
Məsələlər

Граф-турнир

Граф-турнир

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

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

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

Giriş verilənləri

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

Çıxış verilənləri

Выведите -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).

Nümunə

Giriş verilənləri #1
3
Çıxış verilənləri #1
0 1 0
0 0 1
1 0 0
Mənbə Winter School Kharkov 2013, Day 6 - G.Agapov and I.Fefer