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$.

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