Контест!
В Берляндії проходить щорічне змагання зі спортивного програмування "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.