22137번 - Телепорты 스페셜 저지다국어

2112 год подходил к концу, и вы, вместе с небольшой командной единомышленников, решили отправиться на поиски сокровищ в одну заброшенную страну. Города этой страны соединены дорогами, по которым можно передвигаться в обоих направлениях. Вам известно, что жители этой страны любили закапывать свои сокровища вдоль этих дорог. Поэтому вы хотите проехать по всем дорогам этой страны и найти закопанные сокровища. Вам необходимо заранее составить эффективный план путешествия. Для этого следует выбрать некоторый город, с которого следует начать свое путешествие. Далее, перемещаясь по дорогам, посетить еще некоторые города. Составленный план называется эффективным, если каждая дорога будет посещена вами ровно один раз.

Составление плана осложняется одним фактом. Некоторые пары городов соединены телепортами. Например, если город A и город B соединены телепортом, то, приехав по некоторой дороге в город A, вы сразу же телепортируетесь в город B и можете продолжить движение только по дорогам, которые соединены с городом B. Аналогично, если вы приехали по дороге в город B, то сразу же телепортируетесь в город А и продолжаете движение по дорогам, которые соединены с городом A.

Каждый город может быть соединен телепортом не более чем с одним другим городом. Вам необходимо составить эффективный план путешествия.

Входные данные содержат описание нескольких тестов. Каждый тест имеет следующую структуру. В первой строке содержатся три целых числа n, m, k (1 ≤ n ≤ 10⁵, 1 ≤ m ≤ 10⁵, 0 ≤ k ≤ 10⁵) — количество городов, количество дорог и количество телепортов. В следующих m строках содержатся по два различных числа — номера городов, которые соединяет очередная дорога. Далее в k строках содержатся по два различных числа, описывающие пары городов, которые соединены телепортами.

Между двумя городами может быть несколько дорог. Никакой город не соединен дорогой сам с собой. Никакой город не соединен телепортом сам с собой. Любой город соединен телепортом не более чем с одним другим городом.

Гарантируется, что суммарное количество городов во всех тестах не превышает 10⁵. Аналогично, суммарное количество дорог и суммарное количество телепортов также не превышает 10⁵. Последняя строка входных данных содержит три нуля. Их обрабатывать не нужно.

Для каждого набора данных выведите ответ в следующем формате. Если эффективный план посещения составить нельзя, в единственной строке выведите No. Иначе, в первой строке выведите Yes, а во второй m чисел, обозначающие номера дорог. Дороги следует выводить в том порядке, в котором их надо посетить. Дороги нумеруются с единицы в том порядке, в котором они даны во входных данных. Для каждого теста дороги нумеруются независимо.