Universal Cup Judging System

Universal Cup

Süre Sınırı: 2.5 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

Du får oppgitt en urettet graf som består av $n$ noder og $m$ kanter. Nodene er nummerert fra null: $0, 1, \dots, n - 1$. Du skal behandle $q$ spørringer. Hver spørring oppgir et par $(u, v)$ og ber deg om å fjerne kanten $(u, v)$ fra grafen. Hvis det ikke finnes en slik kant i grafen (for eksempel hvis $u = v$), gjør du ingenting. Etter hver spørring skal du skrive ut om grafen er sammenhengende eller ikke.

Inndata

Inndataene inneholder flere testtilfeller. Den første linjen inneholder et enkelt heltall $t$ ($1 \le t \le 5 \cdot 10^5$), antallet testtilfeller. Beskrivelsen av testtilfellene følger.

Den første linjen i hvert testtilfelle inneholder tre heltall $n$, $m$ og $q$ ($2 \le n \le 10^6$, $1 \le m, q \le 10^6$): antallet henholdsvis noder, kanter og spørringer.

Hver av de neste $m$ linjene inneholder to heltall $u_i$ og $v_i$ ($0 \le u_i, v_i < n$), som representerer en kant mellom $u_i$ og $v_i$. Det er ingen løkker og ingen parallelle kanter i grafen.

Hver av de neste $q$ linjene beskriver en spørring. Spørringsparametrene $u_j$ og $v_j$ oppgis imidlertid ikke direkte. I stedet inneholder den $j$-te av disse linjene to heltall $a_j$ og $b_j$ ($0 \le a_j, b_j < n$). Anta at svaret på den $k$-te spørringen er $c_k = 1$ hvis grafen er sammenhengende, eller $c_k = 0$ ellers. Da genereres $u_j$ og $v_j$ etter formlene:

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

Summen av alle $n$, summen av alle $m$ og summen av alle $q$ over alle testtilfellene overstiger ikke $10^6$.

Utdata

For hvert testtilfelle skal du skrive ut $q$ linjer med heltallene $c_1, \dots, c_q$: svarene på spørringene.

Eksempel

Eksempelinndata 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

Eksempelutdata 1

0
0
1
1
0
0

Merknad

I det første testtilfellet ber spørringene om å slette kantene $(0, 0)$ (den finnes ikke) og $(0, 1)$.

I det andre testtilfellet ber spørringene om å slette kantene $(0, 1)$, $(2, 0)$ (den finnes ikke), $(3, 0)$ og $(0, 3)$ (den er allerede slettet av den forrige operasjonen).

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.