4. Starček skazil spojenie

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

Input:

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

Output:

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.

Input:

3 1
1 2
1
1

Output:

3

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