畀一個由 $n$ 個頂點同 $m$ 條邊組成嘅無向圖。頂點由零開始編號:$0, 1, \dots, n - 1$。你需要處理 $q$ 次詢問。每次詢問會畀出一對頂點 $(u, v)$,並要求你喺圖入面刪除邊 $(u, v)$。如果圖入面冇呢條邊(例如當 $u = v$ 嗰陣),就乜都唔使做。喺每次詢問之後,請輸出張圖係咪連通。
輸入格式
輸入包含多組測試數據。第一行包含一個整數 $t$($1 \le t \le 5 \cdot 10^5$),代表測試數據嘅組數。接住落嚟係各組測試數據嘅描述。
每組測試數據嘅第一行包含三個整數 $n$、$m$ 同 $q$($2 \le n \le 10^6$,$1 \le m, q \le 10^6$):分別代表頂點數、邊數同詢問數。
接住落嚟嘅 $m$ 行,每行包含兩個整數 $u_i$ 同 $v_i$($0 \le u_i, v_i < n$),代表連接 $u_i$ 同 $v_i$ 嘅一條邊。圖入面冇自環,亦冇重邊。
再接住落嚟嘅 $q$ 行,每行描述一個詢問。不過,詢問參數 $u_j$ 同 $v_j$ 唔會直接畀出。相反,呢啲行入面嘅第 $j$ 行包含兩個整數 $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$。
輸出格式
對於每組測試數據,輸出 $q$ 行,包含整數 $c_1, \dots, c_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
說明
喺第一組測試數據入面,詢問要求刪除邊 $(0, 0)$(呢條邊唔存在)同埋 $(0, 1)$。
喺第二組測試數據入面,詢問要求刪除邊 $(0, 1)$、$(2, 0)$(呢條邊唔存在)、$(3, 0)$ 同埋 $(0, 3)$(呢條邊已經喺前一次操作入面被刪除咗)。