Задача №113904. Обновление дата-центров
У компании BigData Inc. есть n дата-центров, пронумерованных от 1 до n , расположенных по всему миру. В этих дата-центрах хранятся данные клиентов компании (как можно догадаться из названия — большие данные!)
Основой предлагаемых компанией BigData Inc. услуг является гарантия возможности работы с пользовательскими данными даже при условии выхода какого-либо из дата-центров компании из доступности. Подобная гарантия достигается путём использования двойной репликации данных. Двойная репликация — это подход, при котором любые данные хранятся в двух идентичных копиях в двух различных дата-центрах.
Про каждого из m клиентов компании известны номера двух различных дата-центров c i , 1 и c i , 2 , в которых хранятся его данные.
Для поддержания работоспособности дата-центра и безопасности данных программное обеспечение каждого дата-центра требует регулярного обновления. Релизный цикл в компании BigData Inc. составляет один день, то есть новая версия программного обеспечения выкладывается на каждый компьютер дата-центра каждый день.
Обновление дата-центра, состоящего из множества компьютеров, является сложной и длительной задачей, поэтому для каждого дата-центра выделен временной интервал длиной в час, в течение которого компьютеры дата-центра обновляются и, как следствие, могут быть недоступны. Будем считать, что в сутках h часов. Таким образом, для каждого дата-центра зафиксировано целое число u j ( 0 ≤ u j ≤ h - 1 ), обозначающее номер часа в сутках, в течение которого j -й дата-центр недоступен в связи с плановым обновлением.
Из всего вышесказанного следует, что для любого клиента должны выполняться условия u c i , 1 ≠ u c i , 2 , так как иначе во время одновременного обновления обоих дата-центров, компания будет не в состоянии обеспечить клиенту доступ к его данным.
В связи с переводом часов в разных странах и городах мира, время обновления в некоторых дата-центрах может сдвинуться на один час вперёд. Для подготовки к непредвиденным ситуациям руководство компании хочет провести учения, в ходе которых будет выбрано некоторое непустое подмножество дата-центров, и время обновления каждого из них будет сдвинуто на один час позже внутри суток (то есть, если u j = h - 1 , то новым часом обновления будет 0 , иначе новым часом обновления станет u j + 1 ). При этом учения не должны нарушать гарантии доступности, то есть, после смены графика обновления должно по-прежнему выполняться условие, что данные любого клиента доступны хотя бы в одном экземпляре в любой час.
Учения — полезное мероприятие, но трудоёмкое и затратное, поэтому руководство компании обратилось к вам за помощью в определении минимального по размеру непустого подходящего подмножества дата-центров, чтобы провести учения только на этом подмножестве.
В первой строке находятся три целых числа n , m и h ( 2 ≤ n ≤ 100 000 , 1 ≤ m ≤ 100 000 , 2 ≤ h ≤ 100 000 ) — число дата-центров компании, число клиентов компании и количество часов в сутках.
Во второй строке вам даны n чисел u 1 , u 2 , ..., u n ( 0 ≤ u j < h ), j -е из которых задаёт номер часа, в который происходит плановое обновление программного обеспечения на компьютерах дата-центра j .
Далее в m строках находятся пары чисел c i , 1 и c i , 2 ( 1 ≤ c i , 1 , c i , 2 ≤ n , c i , 1 ≠ c i , 2 ), задающие номера дата-центров, на которых находятся данные клиента i .
Гарантируется, что при заданном расписании обновлений в дата-центрах любому клиенту в любой момент доступна хотя бы одна копия его данных.
В первой строке выведите минимальное количество дата-центров k ( 1 ≤ k ≤ n ), которые должны затронуть учения, чтобы не потерять гарантию доступности. Во второй строке выведите k различных целых чисел — номера кластеров x 1 , x 2 , ..., x k ( 1 ≤ x i ≤ n ), на которых в рамках учений обновления станут проводиться на час позже. Номера кластеров можно выводить в любом порядке.
Если возможных ответов несколько, разрешается вывести любой из них. Гарантируется, что хотя бы один ответ, удовлетворяющий условиям задачи, существует.
Тесты к этой задаче состоят из трёх групп. Баллы за каждую группу ставятся только при про- хождении всех тестов группы и всех тестов предыдущих групп.
Рассмотрим первый тест из условия. Приведённый ответ является единственным способом провести учения, затронув только один дата-центр. В таком сценарии третий сервер начинает обновляться в первый час дня, и никакие два сервера, хранящие данные одного и того же пользователя, не обновляются в один и тот же час.
С другой стороны, например, сдвинуть только время обновления первого сервера на один час вперёд нельзя — в таком случае данные пользователей 1 и 3 будут недоступны в течение нулевого часа.
3 3 5 4 4 0 1 3 3 2 3 1
1 3
4 5 4 2 1 0 3 4 3 3 2 1 2 1 4 1 3
4 1 2 3 4