29299번 - Экспериментальное лечение 스페셜 저지다국어

문제

После долгих безуспешных попыток поставить диагноз новому пациенту, Хаус решил воспользоваться экспериментальным методом лечения. На протяжении всего периода лечения каждый час Форман предлагал пациенту выбрать одну из двух таблеток. Известно, что спустя полчаса после того, как пациент выпил $n$-ую таблетку, его здоровье резко улучшилось и он чудом выжил. Пациент помнит, сколько таблеток каждого типа он выпил, а Форман помнит все пары таблеток, которые он предлагал пациенту. Чтобы в дальнейшем врачи могли лечить людей с такими же симптомами, как у пациента, Хаус хочет восстановить тип каждой таблетки, выпитой пациентом. За помощью он обратился к вам.

입력

В первой строке задано число таблеток, выпитых пациентом, $n$ и количество различных типов таблеток, которыми обладает больница $m$ (1ドル \le n \le 1000, 2 \le m \le 1000$). В каждой $i$-ой строке, начиная со второй по ($n+1$)-ую, задана пара чисел $a_i,ドル $b_i$ (1ドル \le a_i, b_i \le m,ドル $a_i \ne b_i$) --- номера типов таблеток, которые предлагал Форман на ($i-1$)-ом часу. В последней строке задано $m$ чисел $c_j$ --- количество выпитых пациентом таблеток того типа, номер которого равен $j$ (0ドル \le c_j \le n$). Номера типов таблеток начинаются с 1ドル$.

출력

Выведите последовательность из $n$ чисел, где $i$-ое число равно номеру типа таблетки, выпитой на $i$-ом часу. Если ответов несколько, выведите любой. Если ответов не существует, выведите единственное число $-1$.

제한

힌트