Установка модулей GAIA
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Всего есть $$$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$$$.

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

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач, а также тесты из условия успешно пройдены.

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
19$$$n \leqslant 3$$$полная
214$$$n \leqslant 18$$$1полная
314$$$p_i = i$$$ для всех $$$i$$$полная
417$$$m \leqslant 1$$$полная
521$$$q_{p_i} = i$$$ для всех $$$i$$$полная
625нет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