Fisierul de intrare $tequila.in$ va contine pe prima linie doua numere naturale <tex> N </tex> si <tex> M </tex>, reprezantand numarul de angajati ai firmei si, respectiv, numarul de update-uri;
Urmatoarea linie va contine <tex> N </tex> numere naturale - pentru fiecare angajat <tex> X </tex> (<tex> 1 \leq X \leq N </tex>) valoarea asociata initial, <tex> val_X </tex>;
Urmatoarele <tex> N </tex> linii vor descrie firma - pentru fiecare angajat <tex> X </tex> (<tex> 1 \leq X \leq N </tex>), seful direct al acestuia;

Urmatoarele <tex> M </tex> linii vor descrie operatiile de update sub forma: <tex> X \: Y </tex> (noua valoare asociata lui <tex> X </tex> este <tex> Y </tex>, echivalent cu <tex> val_X = Y </tex>);

Urmatoarele <tex> M </tex> linii vor descrie operatiile de update sub forma: <tex> X \: Y </tex> (noua valoare asociata lui <tex> X </tex> este <tex> Y </tex>, echivalent cu <tex> val_X = Y </tex>).

h2. Date de ieşire

h2. Restricţii si precizari

* $1 ≤ val{~X~} ≤ 100.000$ ({$1 ≤ X ≤ N$})

* <tex> 1 \leq val_X \leq 100 \: 000 (1 \leq X \leq N) </tex>

* Seful suprem va avea seful direct codificat cu $-1$.

* Seful suprem va avea seful direct codificat cu <tex> -1 </tex>.

* Fie $Y$ seful direct al angajatului $X$. Spunem ca un angajat este **sef indirect** al lui $X$ daca acesta este fie $Y$, fie un sef indirect al lui $Y$.

* Fie <tex> Y </tex> seful direct al angajatului <tex> X </tex>. Spunem ca un angajat este **sef indirect** al lui <tex> X </tex> daca acesta este fie <tex> Y </tex>, fie un sef indirect al lui <tex> Y </tex>.

* Dupa o operatie de query, Zetul va angaja la loc toti membrii firmei.

* Antonio foloseste mult expresia "pe mangleala" si cuvantul "gen".
* **Subtask 1 (30 puncte)**: <tex> 1 \leq N \leq 20 </tex>, <tex> M = 0 </tex>

* **Subtask 2 (20 puncte)**: <tex> 1 \leq N \cdot M \leq 4.000.000$ </tex>, <tex> 1 \leq M \leq 4.000 </tex> si nu vor exista $2$ angajati cu acelasi sef direct
* **Subtask 3 (50 puncte)**: <tex> 1 \leq N \leq 100.000 </tex>, <tex> 1 \leq M \leq 100.000 </tex>

* **Subtask 2 (20 puncte)**: <tex> 1 \leq N \cdot M \leq 4 \: 000 \: 000$ </tex>, <tex> 1 \leq M \leq 4.000 </tex> si nu vor exista $2$ angajati cu acelasi sef direct
* **Subtask 3 (50 puncte)**: <tex> 1 \leq N \leq 100 \: 000 </tex>, <tex> 1 \leq M \leq 100 \: 000 </tex>

h2. Exemplu