GAIA Module Installation

The GAIA system has $n$ modules, named MINERVA, AETHER, and others. The modules are numbered from 1 to $n$, and there are exactly $n$ slots for connecting them to GAIA. Initially, module $i$ is connected to slot $i$.

There are only two operations that rearrange modules across slots. They are described by permutations $p$ and $q$ of length $n$. Operation $p$ moves the module connected to slot $p_i$ into slot $i$. Operation $q$ works the same way: the module connected to slot $q_i$ is reconnected to slot $i$.

For GAIA to work correctly, each module must be assigned a slot using a partial composition of $p$ and $q$. That means that for each $i$, slot $i$ must be connected to either

• the module obtained by applying $p$, or
• the module obtained by applying $p$ and then $q$.

In other words, slot $i$ can hold module $p_i$ or module $(q \circ p)_i = q_{p_i}$. The choice can be made independently for each $i$.

There are also $m$ system constraints. Each one says that module $a_i$ cannot be placed in a slot adjacent to module $b_i$.

The first line contains two integers $n$ and $m$ ($1 \leqslant n \leqslant 2 \cdot 10^5$; $0 \leqslant m \leqslant 2 \cdot 10^5$), the number of modules and the number of constraints.

The second and third lines contain the elements of permutations $p$ and $q$ ($1 \leqslant p_i, q_i \leqslant n$). Each number from 1 to $n$ appears exactly once in each line.

Each of the following $m$ lines contains two integers $a_i$ and $b_i$ ($1 \leqslant a_i, b_i \leqslant n$; $a_i \neq b_i$), the modules that must not be in adjacent slots.

If no valid assignment exists, print $-1$.

Otherwise, print $n$ integers separated by spaces. The $i$-th integer is 1 if slot $i$ uses the assignment from $p$, and 2 if it uses the assignment from $q \circ p$.

If several valid assignments exist, print any of them.