echival1

Cerință

Fie mulţimea $M= \{1, 2, 3, \dots , n \}$. Vom defini o bipermutare de ordin $n$ ca o matrice $a$ cu două linii şi $n$ coloane, în care fiecare număr $k$ al mulţimii $M$ apare în matrice pe două coloane distincte (figurile $1$, $2$, $3$ şi $4$ conţin câte o bipermutare, iar matricea din figura $0$ nu este bipermutare).
Într-o bipermutare putem efectua următoarele operaţii:

1. să schimbăm două elemente de pe o aceeaşi coloană (figura $1 \rightarrow$ figura $2$)
2. să schimbăm două coloane între ele (figura $1 \rightarrow$ figura $3$)
3. să schimbăm în bipermutare două valori distincte $x$ şi $y$ între ele (figura $1 \rightarrow$ figura $4$)

Două bipermutări sunt echivalente, dacă există o succesiune de operaţii prin care din prima bipermutare se poate ajunge la a doua bipermutare. În figurile de mai sus toate cele patru bipermutări sunt echivalente.
Dacă două bipermutări sunt echivalente, atunci ele aparţin aceleiaşi clase de echivalenţă.

Dându-se o bipermutare de ordin $n$ verificaţi echivalenţa acesteia cu alte $10$ bipermutări de ordin $n$.

Date de intrare

Fişierul de intrare echival1.in conţine pe prima linie numărul natural $n$, cu semnificaţia de mai sus. Următoarele $2$ linii conţin câte $n$ numere separate prin spaţiu şi descriu bipermutarea ce urmează a fi verificată, următoarele $20$ de linii descriu analog cele $10$ bipermutări ale setului, câte una pe două linii.

Date de ieșire

Fişierul de ieşire echival1.out va conţine pe $10$ linii consecutive, în ordinea bipermutărilor citite din fişierul de intrare, câte un număr natural astfel: $1$, dacă bipermutarea curentă este echivalentă cu prima bipermutare citită şi $0$, în caz contrar.

Restricții și precizări

• $3 \leq n \leq 100 \ 000$;
• Problema valora $50$ de puncte în concurs

Exemplul 1

echival1.in

5
5 3 4 1 2
2 4 1 3 5
5 2 4 4 1
3 1 5 3 2
1 1 2 3 4
2 4 5 5 3
1 1 5 3 4
4 3 2 2 5
2 1 3 4 4
1 5 2 3 5
3 2 4 1 1
5 3 2 4 5
3 4 5 5 1
4 2 3 1 2
1 3 2 3 4
4 1 5 5 2
5 2 5 1 1
3 4 2 4 3
4 4 5 2 1
1 2 3 3 5
3 5 3 2 2
1 1 5 4 4

echival1.out

1
0
0
0
0
0
0
0
0
1

Explicație

Prima bipermutare este $\begin{pmatrix} 5 & 3 & 4 & 1 & 2\\ 2 & 4 & 1 & 3 & 5 \end{pmatrix}$.
Dintre următoarele $10$ bipermutări doar prima și ultima este echivalentă cu această bipermutare.

Bipermutarea $\begin{pmatrix} 5 & 3 & 4 & 1 & 2\\ 2 & 4 & 1 & 3 & 5 \end{pmatrix}$ este echivalentă cu bipermutarea $\begin{pmatrix} 5 & 2 & 4 & 4 & 1\\ 3 & 1 & 5 & 3 & 2 \end{pmatrix}$.

$\begin{pmatrix} 5 & 3 & 4 & 1 & 2\\ 2 & 4 & 1 & 3 & 5 \end{pmatrix} \xrightarrow{2} \begin{pmatrix} 3 & 5 & 4 & 1 & 2\\ 4 & 2 & 1 & 3 & 5 \end{pmatrix} \xrightarrow{3} \begin{pmatrix} 5 & 3 & 4 & 1 & 2\\ 4 & 2 & 1 & 5 & 3 \end{pmatrix} \xrightarrow{3} \begin{pmatrix} 5 & 4 & 3 & 1 & 2\\ 3 & 2 & 1 & 5 & 4 \end{pmatrix} \xrightarrow{3} \begin{pmatrix} 5 & 2 & 3 & 1 & 4\\ 3 & 4 & 1 & 5 & 2 \end{pmatrix} \xrightarrow{1} \begin{pmatrix} 5 & 2 & 3 & 4 & 1\\ 3 & 1 & 4 & 5 & 2 \end{pmatrix} \xrightarrow{2} \begin{pmatrix} 5 & 2 & 4 & 4 & 1\\ 3 & 1 & 5 & 3 & 2 \end{pmatrix}$

Bipermutările $\begin{pmatrix} 5 & 3 & 4 & 1 & 2\\ 2 & 4 & 1 & 3 & 5 \end{pmatrix}$ și $\begin{pmatrix} 1 & 1 & 2 & 3 & 4\\ 2 & 4 & 5 & 5 & 3 \end{pmatrix}$ nu sunt echivalente.