Universal Cup Judging System

Universal Cup

時間限制: 2.5 s 記憶體限制: 1024 MB 總分: 100 可 Hack ✓
统计

Du får en oriktad graf som består av $n$ hörn och $m$ kanter. Hörnen är numrerade från noll: $0, 1, \dots, n - 1$. Du ska behandla $q$ frågor. Varje fråga ger ett par $(u, v)$ och ber dig ta bort kanten $(u, v)$ från grafen. Om det inte finns någon sådan kant i grafen (till exempel om $u = v$), gör ingenting. Efter varje fråga ska du skriva ut huruvida grafen är sammanhängande eller inte.

Indata

Indata innehåller flera testfall. Den första raden innehåller ett enda heltal $t$ ($1 \le t \le 5 \cdot 10^5$), antalet testfall. Beskrivningen av testfallen följer.

Den första raden i varje testfall innehåller tre heltal $n$, $m$ och $q$ ($2 \le n \le 10^6$, $1 \le m, q \le 10^6$): antalet hörn, kanter respektive frågor.

Var och en av de följande $m$ raderna innehåller två heltal $u_i$ och $v_i$ ($0 \le u_i, v_i < n$), som representerar en kant mellan $u_i$ och $v_i$. Det finns inga öglor och inga parallella kanter i grafen.

Var och en av de följande $q$ raderna beskriver en fråga. Frågeparametrarna $u_j$ och $v_j$ ges dock inte direkt. Istället innehåller den $j$-te av dessa rader två heltal $a_j$ och $b_j$ ($0 \le a_j, b_j < n$). Antag att svaret på den $k$-te frågan är $c_k = 1$ om grafen är sammanhängande eller $c_k = 0$ annars. Då genereras $u_j$ och $v_j$ enligt formlerna:

$$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.$$

Summan av alla $n$, summan av alla $m$ och summan av alla $q$ över alla testfall överstiger inte $10^6$.

Utdata

För varje testfall, skriv ut $q$ rader med heltalen $c_1, \dots, c_q$: svaren på frågorna.

Exempel

Exempelindata 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

Exempelutdata 1

0
0
1
1
0
0

Notering

I det första testfallet ber frågorna om att ta bort kanterna $(0, 0)$ (den existerar inte) och $(0, 1)$.

I det andra testfallet ber frågorna om att ta bort kanterna $(0, 1)$, $(2, 0)$ (den existerar inte), $(3, 0)$ och $(0, 3)$ (den har redan tagits bort av föregående operation).

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.