$n$ 個の頂点と $m$ 本の辺からなる無向グラフが与えられます。頂点には $0$ から順に $0, 1, \dots, n - 1$ と番号が付けられています。$q$ 個のクエリを処理してください。各クエリではペア $(u, v)$ が与えられ、グラフから辺 $(u, v)$ を削除することが求められます。そのような辺がグラフに存在しない場合(たとえば $u = v$ の場合など)は、何もしません。各クエリの後、グラフが連結であるかどうかを出力してください。
入力
入力は複数のテストケースからなります。1 行目にはテストケースの個数を表す単一の整数 $t$($1 \le t \le 5 \cdot 10^5$)が与えられます。続いて各テストケースの記述が与えられます。
各テストケースの 1 行目には、それぞれ頂点数、辺数、クエリ数を表す 3 つの整数 $n$, $m$, $q$($2 \le n \le 10^6$, $1 \le m, q \le 10^6$)が与えられます。
続く $m$ 行にはそれぞれ 2 つの整数 $u_i$ と $v_i$($0 \le u_i, v_i < n$)が与えられ、頂点 $u_i$ と $v_i$ の間の辺を表します。グラフに自己ループや多重辺は存在しません。
続く $q$ 行はそれぞれクエリを表します。ただし、クエリのパラメータ $u_j$ と $v_j$ は直接与えられません。その代わり、これらのうちの $j$ 行目には 2 つの整数 $a_j$ と $b_j$($0 \le a_j, b_j < n$)が与えられます。$k$ 番目のクエリに対する答えを、グラフが連結ならば $c_k = 1$、そうでなければ $c_k = 0$ とします。このとき、$u_j$ と $v_j$ は次の式に従って生成されます:
$$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.$$
すべてのテストケースにわたる $n$ の総和、$m$ の総和、および $q$ の総和はいずれも $10^6$ を超えません。
出力
各テストケースについて、クエリの答えである整数 $c_1, \dots, c_q$ を $q$ 行に出力してください。
入出力例
入力例 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
出力例 1
0 0 1 1 0 0
ノート
1 つ目のテストケースでは、クエリは辺 $(0, 0)$(存在しない)および辺 $(0, 1)$ の削除を要求しています。
2 つ目のテストケースでは、クエリは辺 $(0, 1)$、辺 $(2, 0)$(存在しない)、辺 $(3, 0)$、および辺 $(0, 3)$(直前の操作ですでに削除されている)の削除を要求しています。