C. Обновление дата-центров
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У компании BigData Inc. есть n дата-центров, пронумерованных от 1 до n, расположенных по всему миру. В этих дата-центрах хранятся данные клиентов компании (как можно догадаться из названия — большие данные!)

Основой предлагаемых компанией BigData Inc. услуг является гарантия возможности работы с пользовательскими данными даже при условии выхода какого-либо из дата-центров компании из доступности. Подобная гарантия достигается путём использования двойной репликации данных. Двойная репликация — это подход, при котором любые данные хранятся в двух идентичных копиях в двух различных дата-центрах.

Про каждого из m клиентов компании известны номера двух различных дата-центров ci, 1 и ci, 2, в которых хранятся его данные.

Для поддержания работоспособности дата-центра и безопасности данных программное обеспечение каждого дата-центра требует регулярного обновления. Релизный цикл в компании BigData Inc. составляет один день, то есть новая версия программного обеспечения выкладывается на каждый компьютер дата-центра каждый день.

Обновление дата-центра, состоящего из множества компьютеров, является сложной и длительной задачей, поэтому для каждого дата-центра выделен временной интервал длиной в час, в течение которого компьютеры дата-центра обновляются и, как следствие, могут быть недоступны. Будем считать, что в сутках h часов. Таким образом, для каждого дата-центра зафиксировано целое число uj (0 ≤ uj ≤ h - 1), обозначающее номер часа в сутках, в течение которого j-й дата-центр недоступен в связи с плановым обновлением.

Из всего вышесказанного следует, что для любого клиента должны выполняться условия uci, 1 ≠ uci, 2, так как иначе во время одновременного обновления обоих дата-центров, компания будет не в состоянии обеспечить клиенту доступ к его данным.

В связи с переводом часов в разных странах и городах мира, время обновления в некоторых дата-центрах может сдвинуться на один час вперёд. Для подготовки к непредвиденным ситуациям руководство компании хочет провести учения, в ходе которых будет выбрано некоторое непустое подмножество дата-центров, и время обновления каждого из них будет сдвинуто на один час позже внутри суток (то есть, если uj = h - 1, то новым часом обновления будет 0, иначе новым часом обновления станет uj + 1). При этом учения не должны нарушать гарантии доступности, то есть, после смены графика обновления должно по-прежнему выполняться условие, что данные любого клиента доступны хотя бы в одном экземпляре в любой час.

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

Входные данные

В первой строке находятся три целых числа n, m и h (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000, 2 ≤ h ≤ 100 000) — число дата-центров компании, число клиентов компании и количество часов в сутках.

Во второй строке вам даны n чисел u1, u2, ..., un (0 ≤ uj < h), j-е из которых задаёт номер часа, в который происходит плановое обновление программного обеспечения на компьютерах дата-центра j.

Далее в m строках находятся пары чисел ci, 1 и ci, 2 (1 ≤ ci, 1, ci, 2 ≤ n, ci, 1 ≠ ci, 2), задающие номера дата-центров, на которых находятся данные клиента i.

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

Выходные данные

В первой строке выведите минимальное количество дата-центров k (1 ≤ k ≤ n), которые должны затронуть учения, чтобы не потерять гарантию доступности. Во второй строке выведите k различных целых чисел — номера кластеров x1, x2, ..., xk (1 ≤ xi ≤ n), на которых в рамках учений обновления станут проводиться на час позже. Номера кластеров можно выводить в любом порядке.

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

Примеры
Входные данные
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
Примечание

Рассмотрим первый тест из условия. Приведённый ответ является единственным способом провести учения, затронув только один дата-центр. В таком сценарии третий сервер начинает обновляться в первый час дня, и никакие два сервера, хранящие данные одного и того же пользователя, не обновляются в один и тот же час.

С другой стороны, например, сдвинуть только время обновления первого сервера на один час вперёд нельзя — в таком случае данные пользователей 1 и 3 будут недоступны в течение нулевого часа.