Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš koľko si dostal/a bodov. Ak si takýto typ úloh ešte nikdy neriešil/a skús sa pozrieť ako by mal vyzerať ideálny program. Ak zaťiaľ programovať nevieš, ale chcel/a by si vedieť, možeš skúsiť náš python tutoriál.

Toto je pokračovanie úlohy z minulého kola. Pri riešenení tejto úlohy môžete využívať napr. vzorové riešenie tejto úlohy.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Kubovi na email [email protected]

Možno si z minulej úlohy pamätáte príbeh obce Alhirkuz. Nedávno tam začali na komunikáciu používať sériové spojenie. To im funguje výborne. Babky sa vedia o panviciach hádať bleskovou rýchlosťou, videá už nemusia byť na DVDčkach a všetci si vedia vyskúšať nové hry na počítači. Jednoducho povedané, všetko funguje a všetci občania sú šťastní.

Teda skoro všetci. Starček, ktorý predtým spravoval posielanie správ stratil kvôli sériovému spojeniu svoju prácu. To sa mu samozrejme nepáčilo, a tak prišiel s plánom, ako získať svoju starú prácu späť. Pokazí sériové spojenie, a tak sa bude musieť obec vrátiť k starému spôsobu komunikácie.

Aby sa sériové spojenie nepokazilo úplne, úradníci potrebujú po každom zásahu starčeka vedieť, na koľko častí je sieť spojení rozdelená. Vedeli by ste im to povedať?

Úloha

V obci máme $n$ domov, ktoré sú očíslované od $1$ po $n$. Medzi niektorými domami je sériové spojenie. Starček sa rozhodol, že pokazí $q$ spojení. Po každom pokazenom spojení chceme vedieť, na koľko častí je sieť rozdelená.

Ako časť siete považujeme skupinu domov v ktorej sa vie správa dostať z každého domu do každého domu (cesta môže prechádzať aj cez iné domy).

Formát vstupu

Na prvom riadku je dvojica čísel $n$ a $m$.
Nasleduje $m$ riadkov na ktorých sú dvojice čísel $a_i$ a $b_i$ popisujúce spojenie medzi domami $a_i$ a $b_i$. Tieto spojenia sú postupne očíslované od $1$ po $m$ v poradí, v akom sú na vstupe.
Na ďalšom riadku je číslo $q$ oznacujúce počet spojení, ktoré starček pokazí.
Nasleduje posledný riadok s $q$ medzerami oddelenými číslami $i_1, i_2, \dots, i_q$ označujúcimi čísla spojení, ktoré starček postupne pokazí.

Formát výstupu

Na výstup vypíšte $q$ čísel oddelených medzerami, ktoré budú oznacovať počet častí, na ktoré je sieť rozdelená po každom pokazenom spojení.

Hodnotenie

Existuje 5 sád vstupov, za každú z nich môžete získať 20 bodov. Pre jednotlivé sady vstupov platia nasledovné obmedzenia:

V každej sade navyše platí $1 \leq q \leq m$.

Príklad

4 4
1 2
2 3
1 3
3 4
3
2 4 3

1 2 3

Po pokazení spojenia číslo 2 sieť zostane ako jedna časť, lebo medzi domami 2 a 3 je ešte spojenie prechádzajúce cez dom 1. Keď sa spojenie číslo 4 pokazí, sieť sa rozdelí na dve časti, pretože dom 4 už nebude spojený s žiadnym domom.
Po pokazení spojenia číslo 3 sa dom 3 oddelí od ostatných domov a sieť sa rozdelí na tri časti.

3 1
1 2
1
1

3

Starček pokazí jediné spojenie, ktoré je v obci. Sieť sa preto rozdelí na individuálne časti pre každý dom.