Всего есть $$$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$$$ должен быть подключен
Иными словами, к слоту номер $$$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$$$.
Если есть несколько подходящих вариантов назначений, выведите любой из них.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач, а также тесты из условия успешно пройдены.
Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
1 | 9 | $$$n \leqslant 3$$$ | – | полная |
2 | 14 | $$$n \leqslant 18$$$ | 1 | полная |
3 | 14 | $$$p_i = i$$$ для всех $$$i$$$ | – | полная |
4 | 17 | $$$m \leqslant 1$$$ | – | полная |
5 | 21 | $$$q_{p_i} = i$$$ для всех $$$i$$$ | – | полная |
6 | 25 | нет | 1 – 5 | первая ошибка |
3 1 3 1 2 2 1 3 1 3
1 2 2
3 1 1 2 3 3 2 1 1 2
-1
4 2 3 4 1 2 4 1 3 2 1 2 3 4
1 2 2 2