Anda diberikan sebuah graf tak berarah yang terdiri dari $n$ titik sudut (simpul) dan $m$ sisi. Simpul-simpulnya dinomori dari nol: $0, 1, \dots, n - 1$. Anda diminta untuk memproses $q$ kueri. Setiap kueri memberikan pasangan $(u, v)$ dan meminta Anda untuk menghapus sisi $(u, v)$ dari graf. Jika tidak ada sisi seperti itu di dalam graf (misalnya, jika $u = v$), jangan lakukan apa pun. Setelah setiap kueri, cetak apakah graf tersebut terhubung atau tidak.
Masukan
Masukan berisi beberapa kasus uji. Baris pertama berisi sebuah bilangan bulat $t$ ($1 \le t \le 5 \cdot 10^5$), banyaknya kasus uji. Deskripsi dari masing-masing kasus uji menyusul.
Baris pertama dari setiap kasus uji berisi tiga bilangan bulat $n$, $m$, dan $q$ ($2 \le n \le 10^6$, $1 \le m, q \le 10^6$): masing-masing adalah banyaknya simpul, sisi, dan kueri.
Masing-masing dari $m$ baris berikutnya berisi dua bilangan bulat $u_i$ dan $v_i$ ($0 \le u_i, v_i < n$), yang merepresentasikan sebuah sisi antara $u_i$ dan $v_i$. Tidak ada loop dan tidak ada sisi paralel di dalam graf.
Masing-masing dari $q$ baris berikutnya menjelaskan sebuah kueri. Namun, parameter kueri $u_j$ dan $v_j$ tidak diberikan secara langsung. Sebagai gantinya, baris ke-$j$ dari baris-baris ini berisi dua bilangan bulat $a_j$ dan $b_j$ ($0 \le a_j, b_j < n$). Misalkan jawaban untuk kueri ke-$k$ adalah $c_k = 1$ jika graf terhubung atau $c_k = 0$ jika sebaliknya. Maka $u_j$ dan $v_j$ dibangkitkan menurut rumus:
$$u_j = (2^{j-2}c_1 + 2^{j-3}c_2 + \dots + 2^1 c_{j-2} + 2^0 c_{j-1} + a_j) \bmod n,$$
$$v_j = (3^{j-2}c_1 + 3^{j-3}c_2 + \dots + 3^1 c_{j-2} + 3^0 c_{j-1} + b_j) \bmod n.$$
Jumlah semua $n$, jumlah semua $m$, dan jumlah semua $q$ di seluruh kasus uji tidak melebihi $10^6$.
Keluaran
Untuk setiap kasus uji, cetak $q$ baris dengan bilangan bulat $c_1, \dots, c_q$: jawaban untuk kueri-kueri tersebut.
Contoh
Contoh Masukan 1
2 3 1 2 0 1 0 0 0 1 4 4 4 0 1 1 2 2 3 0 3 0 1 1 3 0 0 2 3
Contoh Keluaran 1
0 0 1 1 0 0
Catatan
Pada kasus uji pertama, kueri meminta untuk menghapus sisi $(0, 0)$ (sisi tersebut tidak ada) dan $(0, 1)$.
Pada kasus uji kedua, kueri meminta untuk menghapus sisi $(0, 1)$, $(2, 0)$ (sisi tersebut tidak ada), $(3, 0)$, dan $(0, 3)$ (sisi tersebut sudah dihapus oleh operasi sebelumnya).