Di suatu galaksi yang jauh di alam semesta, terdapat $N$ bintang dengan peradaban maju. Bintang-bintang tersebut diberi nomor dari $1$ sampai $N$. Setiap bintang mengelola satu pesawat antariksa. Setiap pesawat berada dalam salah satu dari dua keadaan: sedang digunakan untuk pergi ke suatu bintang lain, atau sedang tidak digunakan. Jika pesawat yang dikelola bintang $a$ sedang digunakan untuk pergi ke bintang $b$, pesawat itu melakukan perjalanan bolak-balik antara bintang $a$ dan bintang $b$ berulang kali. Ketika pesawat pergi dari bintang $a$ ke bintang $b$, penumpang umum dapat menaikinya untuk pergi dari $a$ ke $b$. Namun, ketika pesawat kembali dari $b$ ke $a$, penumpang umum tidak dapat menaikinya karena persoalan bahan bakar, pengangkutan barang, dan sebagainya. Selain itu, ketika pesawat yang dikelola bintang $a$ tidak digunakan, pesawat itu menunggu di bintang $a$.

Saat ini, semua pesawat sedang tidak digunakan. Jadwal perubahan keadaan pesawat di masa mendatang telah ditentukan. Setiap perubahan keadaan adalah salah satu dari jenis berikut.

• Mengubah pesawat yang dikelola bintang $a$, yang sedang tidak digunakan, menjadi sedang digunakan untuk pergi ke bintang $b$. Namun, perubahan ini hanya dilakukan jika penumpang umum tidak dapat pergi dari bintang $b$ ke bintang $a$ dengan menaiki pesawat antariksa beberapa kali.
• Mengubah pesawat yang dikelola bintang $a$, yang sedang digunakan, menjadi tidak digunakan.

Dua orang yang berencana menjelajahi galaksi ini menyiapkan beberapa pertanyaan berikut untuk merencanakan pertemuan mereka.

• Pada suatu saat dalam jadwal, jika satu orang berada di bintang $a$ dan satu orang lagi berada di bintang $b$, dapatkah mereka bertemu dengan menggunakan pesawat sebagai penumpang umum? Jika bisa, di bintang manakah mereka sebaiknya bertemu agar jumlah penggunaan pesawat paling sedikit? Dengan kata lain, adakah bintang $c$ yang dapat dicapai penumpang umum dari bintang $a$ maupun bintang $b$ dengan menaiki pesawat beberapa kali? Jika ada, bintang $c$ manakah yang meminimalkan jumlah penggunaan pesawat untuk pergi dari $a$ ke $c$ ditambah jumlah penggunaan pesawat untuk pergi dari $b$ ke $c$?

Sebagai pemrogram yang andal, Anda diminta mencari jawaban atas semua pertanyaan kedua orang tersebut.

Tugas

Buatlah program yang menjawab pertanyaan-pertanyaan tersebut, jika diberikan jadwal perubahan keadaan pesawat di masa mendatang dan pertanyaan dalam urutan kronologis.

Masukan

Bacalah masukan berikut dari masukan standar.

• Baris pertama berisi bilangan bulat $N,Q$, dipisahkan oleh spasi. Banyaknya bintang adalah $N$, dan jumlah perubahan keadaan ditambah banyaknya pertanyaan adalah $Q$.
• $Q$ baris berikutnya menyatakan perubahan keadaan dan pertanyaan dalam urutan kronologis. Baris ke-$i$ di antaranya ($1 \le i \le Q$) berisi dua atau tiga bilangan bulat yang dipisahkan oleh spasi. Misalkan bilangan bulat pertama adalah $T_i$. Baris tersebut termasuk salah satu kasus berikut.

(i) Jika $T_i=1$

Baris ini berisi bilangan bulat $T_i,A_i,B_i$ dan menyatakan perubahan keadaan berikut: pesawat yang dikelola bintang $A_i$ menjadi digunakan untuk pergi ke bintang $B_i$.

Dijamin bahwa $1 \le A_i \le N$, $1 \le B_i \le N$, dan $A_i \ne B_i$; pesawat yang dikelola bintang $A_i$ sedang tidak digunakan saat ini; dan penumpang umum tidak dapat pergi dari bintang $B_i$ ke bintang $A_i$ dengan menaiki pesawat beberapa kali saat ini.

(ii) Jika $T_i=2$

Baris ini berisi bilangan bulat $T_i,A_i$ dan menyatakan perubahan keadaan berikut: pesawat yang dikelola bintang $A_i$ menjadi tidak digunakan.

Dijamin bahwa $1 \le A_i \le N$ dan pesawat yang dikelola bintang $A_i$ sedang digunakan saat ini.

(iii) Jika $T_i=3$

Baris ini berisi bilangan bulat $T_i,A_i,B_i$ dan menyatakan pertanyaan berikut: jika saat ini satu orang berada di bintang $A_i$ dan satu orang lagi berada di bintang $B_i$, dapatkah mereka bertemu dengan menggunakan pesawat sebagai penumpang umum? Jika bisa, di bintang manakah mereka sebaiknya bertemu agar jumlah penggunaan pesawat paling sedikit?

Dijamin bahwa $1 \le A_i \le N$, $1 \le B_i \le N$, dan $A_i \ne B_i$.

Keluaran

Untuk setiap pertanyaan, tuliskan hal berikut ke keluaran standar:

• Jika mereka dapat bertemu, nomor bintang tempat mereka bertemu yang meminimalkan jumlah penggunaan pesawat.
• Jika mereka tidak dapat bertemu, bilangan bulat $-1$.

Tuliskan jawaban sesuai urutan pertanyaan, satu jawaban per baris.

Batasan

Semua data masukan memenuhi kondisi berikut.

• $2 \le N \le 1\,000\,000$.
• $1 \le Q \le 1\,000\,000$.

Subsoal

Subsoal 1 [10 poin]

Kondisi berikut terpenuhi.

• $N \le 5\,000$.
• $Q \le 5\,000$.

Subsoal 2 [30 poin]

• $T_i \ne 2$ ($1 \le i \le Q$).

Subsoal 3 [60 poin]

Tidak ada batasan tambahan.

Contoh

Masukan 1

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

Keluaran 1

-1
4

Penjelasan

Dalam contoh ini, perubahan keadaan dan pertanyaan terjadi dalam urutan berikut.

• Pesawat yang dikelola bintang $2$ menjadi digunakan untuk pergi ke bintang $4$.
• Jika saat ini kedua orang berada di bintang $2$ dan bintang $6$, mereka tidak dapat bertemu, sehingga keluarkan $-1$.
• Pesawat yang dikelola bintang $4$ menjadi digunakan untuk pergi ke bintang $3$.
• Pesawat yang dikelola bintang $6$ menjadi digunakan untuk pergi ke bintang $4$.
• Jika saat ini kedua orang berada di bintang $2$ dan bintang $6$, mereka dapat bertemu di bintang $3$ atau bintang $4$. Untuk meminimalkan jumlah penggunaan pesawat, mereka harus bertemu di bintang $4$, sehingga keluarkan $4$.

Masukan 2

8 36
1 1 2
1 6 5
1 7 8
3 5 6
1 5 4
1 8 1
3 7 2
3 3 8
3 1 8
1 3 2
1 4 1
3 8 5
3 4 3
2 4
3 6 8
1 2 5
3 6 8
2 8
3 1 4
3 6 8
3 6 3
2 3
3 1 2
1 4 3
3 2 6
1 8 3
3 1 7
3 1 6
3 5 4
2 2
2 5
1 3 6
1 2 7
3 1 4
3 1 5
3 6 7

Keluaran 2

5
2
-1
1
1
2
-1
5
4
-1
5
2
5
3
5
4
3
5
6