Подразделы

Другие разделы

Дата и время

23/11/2024 21:15:16

Авторизация

Зарегистрироваться
Восстановить пароль

1028. Репликация

Репликация Рис. 1

Репликация

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

9:02
Угу. Звонок. Пользователи в Питере не могут произвести репликацию. Я определил, что это происходит из-за вспышек на Солнце. Сказал им, чтобы звонили в отдел Телекоммуникаций.

9:30
Господи, еще один юзер! Похож на предыдущего. Говорит, что они в Екатеринбурге не могут произвести репликацию с Питером. Сказал им, что это из-за вспышек на Солнце, но с трехчасовой разницей, так как они в другом часовом поясе. Посоветовал им перевести время на сервере на три часа назад.

10:17
Звонок из Воронежа. Говорят, что не могут перенаправить электронную почту в Екатеринбург. Сказал им, чтобы переставили время на сервере на три часа вперед.

11:00
Пришло мыло от начальства с требованием прекратить переставлять время на серверах. Изменил дату и время и переслал его в Ростов.

16:55
Решил запустить макрос "Создание конфликтов сохранения/репликации", чтобы следующей смене было чем заняться.

На следующий день, 8:30
Закончил читать журнал поддержки ночной смены. Работы им хватало… Просто жуткие конфликты сохранения и репликации всю ночь!

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

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

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

Ввод

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

Вывод

В выходном файле должно содержаться `M` чисел `d_i`, равных `0`, `1` или `2`. `d_i\ =\ 0` означает, что для соответствующего кабеля следует сохранить двустороннюю передачу данных, `d_i\ =\ 1` – что следует фиксировать направление от `a_i` к `b_i`, `d_i\ =\ 2` – что следует фиксировать направление от `b_i` к `a_i`.

Если имеется несколько оптимальных решений, следует вывести любое из них.

Ограничения

`1\ ≤\ N\ ≤\ 2*10^5;\ 0\ ≤\ M\ ≤\ 2*10^5`

Пример ввода 1

Пример вывода 1

2
1
0

Пример ввода 2

Пример вывода 2

1
2
1

Источник: И. Туфанов, А. Кленин, ДВГУ