Подразделы

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

Дата и время

09/04/2025 02:41:19

Авторизация

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

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

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