Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.5 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

Сізге $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$ арасындағы қабырғаны білдіретін екі бүтін сан $u_i$ және $v_i$ ($0 \le u_i, v_i < n$) берілген. Графта ілмектер мен еселі қабырғалар жоқ.

Келесі $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$-нен аспайды.

Шығыс деректері

Әрбір тест жиынтығы үшін сұранымдардың жауаптары болатын $c_1, \dots, c_q$ бүтін сандары бар $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)$ (ол алдыңғы амалмен өшіріліп қойған) қабырғаларын өшіруді сұрайды.

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.