給定一個由 $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)$(該邊已被前一次操作刪除)。