GAIA 모듈 설치

GAIA 시스템에는 MINERVA, AETHER 등의 이름을 가진 모듈이 $n$개 있다. 모듈에는 1부터 $n$까지 번호가 붙어 있고, GAIA에 연결할 슬롯도 정확히 $n$개 있다. 처음에는 모듈 $i$가 슬롯 $i$에 연결되어 있다.

모듈과 슬롯의 배치를 바꾸는 연산은 두 가지뿐이며, 길이 $n$인 순열 $p$와 $q$로 주어진다. 연산 $p$는 슬롯 $p_i$에 연결된 모듈을 슬롯 $i$로 옮긴다. 연산 $q$도 같은 방식으로, 슬롯 $q_i$에 연결된 모듈을 슬롯 $i$에 다시 연결한다.

GAIA가 올바르게 작동하려면 $p$와 $q$의 부분 합성을 써서 각 모듈에 슬롯을 배정해야 한다. 즉 모든 $i$에 대해 슬롯 $i$에는 다음 중 하나가 연결되어 있어야 한다.

• $p$를 적용해서 얻은 모듈
• $p$를 적용한 뒤 $q$를 적용해서 얻은 모듈

다시 말해 슬롯 $i$에는 모듈 $p_i$ 또는 모듈 $(q \circ p)_i = q_{p_i}$를 넣을 수 있다. 각 $i$의 선택은 다른 $i$와 무관하게 할 수 있다.

시스템 제약이 $m$개 주어진다. 각 제약은 모듈 $a_i$를 모듈 $b_i$와 인접한 슬롯에 둘 수 없다는 뜻이다.

첫 줄에 두 정수 $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$개의 줄에는 인접한 슬롯에 놓일 수 없는 모듈 번호 $a_i$와 $b_i$가 주어진다 ($1 \leqslant a_i, b_i \leqslant n$; $a_i \neq b_i$).

가능한 배정이 없으면 $-1$을 출력한다.

그렇지 않으면 공백으로 구분한 정수 $n$개를 출력한다. $i$번째 정수는 슬롯 $i$가 $p$에 해당하는 배정이면 1, $q \circ p$에 해당하는 배정이면 2이다.

조건을 만족하는 배정이 여러 개라면 그중 어느 것을 출력해도 된다.