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

Автор:И. Туфанов, А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

Во входном файле содержатся числа N M, где N — число серверов, M — число кабелей. За ними идут M пар чисел ai bi, — номера серверов, соединённых i-м кабелем. Сервер не может быть соединён сам с собой, но два сервера могут быть соединены несколькими кабелями.

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

В выходном файле должно содержаться M чисел di, равных 0, 1 или 2. di = 0 означает, что для соответствующего кабеля следует сохранить двустороннюю передачу данных, di = 1 — что следует фиксировать направление от ai к bi, di = 2 — что следует фиксировать направление от bi к ai. Если имеется несколько оптимальных решений, следует вывести любое из них.

Ограничения

1 ≤ N ≤ 2 × 105; 0 ≤ M ≤ 2 × 105

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
3 3
1 2
1 2
2 3
 
2
1
0
2 
3 3
1 2
1 3
2 3
 
1
2
1
0.039s 0.008s 15