Universal Cup Judging System

Universal Cup

حد الوقت: 2.5 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

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 đó).

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.