eolymp
bolt
Try our new interface for solving problems
Problems

Контест!

Контест!

Time limit 2 seconds
Memory limit 122 MiB

В Берляндии проходит ежегодное соревнование по спортивному программированию "Berland Open". Как Вам наверняка известно, завтра состоится n четвертьфиналов, в которых примут участие 2n программистов, по двое в каждом четвертьфинале. После соревнования пройдёт процедура награждения, на которую будут приглашены все n победителей.

К сожалению, отношения между программистами в Берляндии весьма натянуты. В частности, есть m пар участников, которые настолько друг друга не любят, что процедура награждения будет сорвана, если на неё попадут два участника из одной пары.

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

Input data

Первая строка содержит два целых неотрицательных числа n и m (0n10^5, 0m10^6). Далее следуют n строк по два числа в каждой - номера участников i-го четвертьфинала. Далее следуют m строк, содержащих по два числа u, v (1u, v2n) каждая, означающих, что u-тый и v-тый программисты конфликтуют и одновременное их попадание на процедуру награждения означает срыв этой процедуры. Одна и та же пара может быть упомянута несколько раз.

Программисты нумеруются натуральными числами от 1 до 2n.

Output data

Если есть хоть один шанс, что процедура награждения пройдёт успешно, то выведите n чисел - номера программистов, которые должны будут участвовать в этой процедуре (если есть несколько вариантов успешного проведения процедуры, выведите любой).

Если выбрать бесконфликтных победителей невозможно, то выведите одно число -1.

Examples

Input example #1
2 1
1 2
3 4
1 3
Output example #1
1 4 
Input example #2
3 4
2 3
1 4
5 6
2 4
1 2
3 6
1 5
Output example #2
3 4 5 
Source 2012 ЛКШ Берендевы Поляны, 2 Августа, Параллель А, День 5