| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 49 | 13 | 12 | 40.000% |
M je kodno ime osobe koja obnaša jednu od ključnih funkcija britanske tajne službe (MI6). Jedna od glavnih zadaća na toj funkciji je analiza sigurnosnih svojstava neprijateljskih komunikacijskih mreža. Ovaj zadatak ocrtava jedan od tipičnih problema s kojima se M dnevno susreće.
Neprijateljska komunikacijska mreža sastoji se od $N$ (naizgled običnih) poštanskih ureda i $M$ dvosmjernih prometnica koje direktno povezuju neke parove poštanskih ureda. Radi jednostavnosti, poštanske urede ćemo označiti prirodnim brojevima od 1ドル$ do $N$.
Kada neprijatelj želi poslati tajnu informaciju iz ureda s oznakom $a$ do ureda s oznakom $b,ドル tajni agent će sjesti u lažno vozilo pošte i provozati se nekim nizom prometnica koje tvore put između ta dva poštanska ureda. Par poštanskih ureda $(a, b)$ smatra se ranjivim ako postoji neka cesta po kojoj će tajni agent sigurno morati proći na svom putovanju od ureda $a$ do ureda $b,ドル ili ako uopće ne postoji put između ta dva ureda.
M se danas bavi analizom povijesne ranjivosti jedne takve mreže. Naime, M je prikupio informacije o povijesnom razvoju mreže, što znači da zna kojim su se redoslijedom gradile prometnice između poštanskih ureda. Sada ga za neke parove ureda zanima u kojem su trenutku (ako uopće) prestali biti ranjivi.
U prvom su retku brojevi $N$ i $M$ iz teksta zadatka.
U $i$-tom od idućih $M$ redaka su $x_i$ i $y_i$ koji označavaju da je $i$-ta izgrađena prometnica povezivala poštanske urede s oznakama $x_i$ i $y_i$ ($x_i ≠ y_i$).
Moguće je da više od jedne prometnice povezuje isti par poštanskih ureda.
U sljedećem se retku nalazi prirodan broj $Q$ koji označava broj upita na koje $M$ želi dobiti odgovor.
U $j$-tom od sljedećih $Q$ redaka su različiti brojevi $a_j$ i $b_j$ koji definiraju $j$-ti upit agenta M. Odnosno, M želi saznati u kojem je trenutku par ureda $(a_j , b_j )$ prestao biti ranjiv.
U $j$-tom retku treba ispisati odgovor na $j$-ti upit agenta M.
Ako je par ureda iz $j$-tog upita i dalje ranjiv, odgovor na $j$-ti upit je $-1$. Inače, odgovor je prirodan broj $k$ koji označava da je par ureda iz upita prestao biti ranjiv nakon izgradnje $k$-te prometnice.
U svim podzadacima vrijedi 2ドル ≤ N ≤ 300,000円,ドル 0ドル ≤ M ≤ 300,000円$ i 1ドル ≤ Q ≤ 300,000円$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $Q = 1$ |
| 2 | 20 | $(x_{2i}, y_{2i}) = (x_{2i-1}, y_{2i-1})$ i $M$ je paran. |
| 3 | 30 | $N, M ≤ 5,000円$ |
| 4 | 40 | Nema dodatnih ograničenja. |
Primijetite da u drugom podzadatku prve dvije prometnice povezuju isti par gradova, druge dvije prometnice povezuju isti par gradova, itd.
3 3 1 2 2 3 3 1 1 1 2
3
3 4 1 2 1 2 2 3 2 3 3 1 2 2 3 3 1
2 4 4
6 7 1 2 2 3 3 4 2 5 3 5 4 5 1 3 5 1 3 2 3 4 5 1 4 2 6
7 5 6 7 -1
Pojašnjenje trećeg probnog primjera: Promatrajmo prvi upit. Do trenutka 6 (uključivo) između ureda 1 i 3 ili nije postojao put, ili je svaki takav put prolazio prometnicom 1. Tek u trenutku 7 to nije slučaj. Za peti upit, između ureda 2 i 6 nikada nije postojao put pa je odgovor -1.