Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1028. Репликация
Компоненты связности, мосты, точки сочлененияОлимпиадные задачи на русском языке
| 03/07/2008 | Лето 2008 дорешивание (11E) |
| 25/07/2008 | Лето 2008 - 11 (День системного администратора) (E) |
| 26/07/2013 | Лето 2013-18 (День системного администратора) (E) |
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
9:02
Угу. Звонок. Пользователи в Питере не могут произвести репликацию. Я определил, что это происходит из-за вспышек на Солнце. Сказал им, чтобы звонили в отдел Телекоммуникаций.
9:30
Господи, еще один юзер! Похож на предыдущего. Говорит, что они в Екатеринбурге не могут произвести репликацию с Питером. Сказал им, что это из-за вспышек на Солнце, но с трехчасовой разницей, так как они в другом часовом поясе. Посоветовал им перевести время на сервере на три часа назад.
10:17
Звонок из Воронежа. Говорят, что не могут перенаправить электронную почту в Екатеринбург. Сказал им, чтобы переставили время на сервере на три часа вперед.
11:00
Пришло мыло от начальства с требованием прекратить переставлять время на серверах. Изменил дату и время и переслал его в Ростов.
16:55
Решил запустить макрос "Создание конфликтов сохранения/репликации", чтобы следующей смене было чем заняться.
На следующий день, 8:30
Закончил читать журнал поддержки ночной смены. Работы им хватало… Просто жуткие конфликты сохранения и репликации всю ночь!
Угу. Звонок. Пользователи в Питере не могут произвести репликацию. Я определил, что это происходит из-за вспышек на Солнце. Сказал им, чтобы звонили в отдел Телекоммуникаций.
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
3 3 1 2 1 2 2 3
Пример вывода 1
2 1 0
Пример ввода 2
3 3 1 2 1 3 2 3
Пример вывода 2
1 2 1
