Задача L. Репликация ≡

Условие

Компьютерная сеть крупного предприятия содержит N серверов баз данных. Некоторые сервера напрямую связаны между собой кабелями локальной сети, при этом от каждого сервера можно добраться по связям до любого другого.

Сервера содержат копии одной и той же базы данных. Чтобы поддерживать эти копии в одинаковом состоянии, используется система репликации — сервер рассылает каждое изменение, внесённое в его данные, всем соседним серверам, те, в свою очередь, рассылают его далее до тех пор, пока об изменении не будет оповещена вся сеть.

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

Рекомендуется рассмотреть частичные решения

• N ≤ 100

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3 3
1 2
1 2
2 3

2
1
0

3 3
1 2
1 3
2 3

1
2
1