Контест!
В Берляндии проходит ежегодное соревнование по спортивному программированию "Berland Open". Как Вам наверняка известно, завтра состоится n четвертьфиналов, в которых примут участие 2n программистов, по двое в каждом четвертьфинале. После соревнования пройдёт процедура награждения, на которую будут приглашены все n победителей.
К сожалению, отношения между программистами в Берляндии весьма натянуты. В частности, есть m пар участников, которые настолько друг друга не любят, что процедура награждения будет сорвана, если на неё попадут два участника из одной пары.
Васе выпала тяжёлая доля вести процедуру награждения и развлекать толпу программистов. Он очень не хочет этого делать и потому очень надеется, что процедура награждения будет сорвана. Сегодня он сумел раздобыть секретный план распределения программистов по n четвертьфиналам. Помогите ему определить, есть ли хоть один шанс, что награждение таки состоится успешно.
Входные данные
Первая строка содержит два целых неотрицательных числа n и m (0 ≤ n ≤ 10^5, 0 ≤ m ≤ 10^6). Далее следуют n строк по два числа в каждой - номера участников i-го четвертьфинала. Далее следуют m строк, содержащих по два числа u, v (1 ≤ u, v ≤ 2n) каждая, означающих, что u-тый и v-тый программисты конфликтуют и одновременное их попадание на процедуру награждения означает срыв этой процедуры. Одна и та же пара может быть упомянута несколько раз.
Программисты нумеруются натуральными числами от 1 до 2n.
Выходные данные
Если есть хоть один шанс, что процедура награждения пройдёт успешно, то выведите n чисел - номера программистов, которые должны будут участвовать в этой процедуре (если есть несколько вариантов успешного проведения процедуры, выведите любой).
Если выбрать бесконфликтных победителей невозможно, то выведите одно число -1.