Bạn được cho một đồ thị vô hướng gồm $n$ đỉnh và $m$ cạnh. Các đỉnh được đánh số từ 0: $0, 1, \dots, n - 1$. Bạn cần xử lý $q$ truy vấn. Mỗi truy vấn cung cấp một cặp $(u, v)$ và yêu cầu bạn xóa cạnh $(u, v)$ khỏi đồ thị. Nếu không có cạnh như vậy trong đồ thị (ví dụ, nếu $u = v$), không làm gì cả. Sau mỗi truy vấn, hãy in ra xem đồ thị có liên thông hay không.
Dữ liệu vào
Dữ liệu vào chứa nhiều bộ test. Dòng đầu tiên chứa một số nguyên duy nhất $t$ ($1 \le t \le 5 \cdot 10^5$), số lượng bộ test. Mô tả của các bộ test theo sau.
Dòng đầu tiên của mỗi bộ test chứa ba số nguyên $n$, $m$ và $q$ ($2 \le n \le 10^6$, $1 \le m, q \le 10^6$): lần lượt là số lượng đỉnh, cạnh và truy vấn.
Mỗi dòng trong $m$ dòng tiếp theo chứa hai số nguyên $u_i$ và $v_i$ ($0 \le u_i, v_i < n$), biểu diễn một cạnh nối giữa $u_i$ và $v_i$. Không có khuyên và không có cạnh bội trong đồ thị.
Mỗi dòng trong $q$ dòng tiếp theo mô tả một truy vấn. Tuy nhiên, các tham số truy vấn $u_j$ và $v_j$ không được cung cấp trực tiếp. Thay vào đó, dòng thứ $j$ trong các dòng này chứa hai số nguyên $a_j$ và $b_j$ ($0 \le a_j, b_j < n$). Giả sử câu trả lời cho truy vấn thứ $k$ là $c_k = 1$ nếu đồ thị liên thông hoặc $c_k = 0$ trong trường hợp ngược lại. Khi đó $u_j$ và $v_j$ được sinh theo công thức:
$$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.$$
Tổng của tất cả $n$, tổng của tất cả $m$, và tổng của tất cả $q$ qua tất cả các bộ test không vượt quá $10^6$.
Kết quả
Đối với mỗi bộ test, in ra $q$ dòng chứa các số nguyên $c_1, \dots, c_q$: câu trả lời cho các truy vấn.
Ví dụ
Dữ liệu vào mẫu 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
Kết quả mẫu 1
0 0 1 1 0 0
Ghi chú
Ở bộ test đầu tiên, các truy vấn yêu cầu xóa các cạnh $(0, 0)$ (không tồn tại) và $(0, 1)$.
Ở bộ test thứ hai, các truy vấn yêu cầu xóa các cạnh $(0, 1)$, $(2, 0)$ (không tồn tại), $(3, 0)$ và $(0, 3)$ (đã bị xóa bởi thao tác trước đó).