28621번 - Установка модулей GAIA 스페셜 저지다국어

문제

Всего есть $n$ модулей системы GAIA, таких как MINERVA, AETHER и другие. Модули пронумерованы от 1ドル$ до $n,ドル и для них есть ровно $n$ слотов для подключения их к GAIA. Изначально модуль номер $i$ подключен к слоту номер $i$.

Существуют только две операции, позволяющие оперировать назначением модулей GAIA по слотам. Эти операции могут быть описаны перестановками $p$ и $q$ длины $n$. В соответствии с операцией $p,ドル модуль, подключенный к слоту $p_i,ドル перемещается в слот $i$. Аналогично для $q$: при применении операции $q,ドル модуль, подключенный к слоту $q_i,ドル переподключается к слоту $i$.

Чтобы GAIA функционировала корректно, требуется назначить каждому модулю слот, используя частичную композицию операций $p$ и $q$. Это означает, что для каждого $i$ к слоту номер $i$ должен быть подключен

• либо модуль, подключаемый к нему применением операции $p$;
• либо модуль, подключаемый к нему применением операции $p,ドル а затем операции $q$.

Иными словами, к слоту номер $i$ может быть подключен либо модуль с номером $p_i,ドル либо модуль с номером $(q \circ p)_i = q_{p_i}$. Для каждого $i$ этот выбор можно сделать независимо от других.

Помимо этого, известны также $m$ системных ограничений вида <<модуль номер $a_i$ не может располагаться на соседнем слоте с модулем $b_i$>>.

Определите, существует ли частичная композиция перестановок $p$ и $q,ドル обеспечивающая корректное функционирование GAIA, то есть при которой

• каждый модуль подключен к своему слоту, и каждый слот занят только одним модулем;
• и удовлетворены все ограничения на расположение модулей в соседних слотах.

입력

В первой строке ввода через пробел даны два целых числа $n$ и $m$ --- количество модулей системы и количество ограничений (1ドル \leqslant n \leqslant 2 \cdot 10^5$; 0ドル \leqslant m \leqslant 2 \cdot 10^5$).

Во второй и третьей строках через пробел перечислены элементы перестановок $p$ и $q,ドル описывающих операции (1ドル \leqslant p_i, q_i \leqslant n$). Гарантируется, что каждое число от 1ドル$ до $n$ встречается в описании каждой операции ровно один раз.

В следующих $m$ строках даны ограничения на расположение модулей: в $i$-й из них через пробел даны два целых числа $a_i$ и $b_i$ --- номера модулей, которые не должны располагаться в соседних слотах (1ドル \leqslant a_i, b_i \leqslant n$; $a_i \neq b_i$).

출력

Если невозможно построить удовлетворяющее условию назначение, выведите <<-1>> (без кавычек).

Иначе выведите через пробел $n$ целых чисел, $i$-е из которых равно 1ドル,ドル если для $i$-го слота выбрано назначение, соответствующее $p,ドル и 2ドル,ドル если выбрано назначение, соответствующее $q \circ p$.

Если есть несколько подходящих вариантов назначений, выведите любой из них.

제한

힌트