25475번 - Hrvati 다국어

문제

Mirko je nedavno u bespućima interneta pronašao legendu kako venama mnogo članova engleske kraljevske obitelji teče i hrvatska krv. Naime, hrvatski velikan Nikola Šubić Zrinski je prapraprapra... pradjed kraljice Elizabete II.

Nakon tog saznanja, odmah se zapitao koliko je točno Hrvatica/Hrvata u engleskoj kraljevskoj obitelji te je postavio to pitanje na jednom poznatom internet forumu. Uskoro mu je stiglo $Q$ odgovora u obliku “Ja znam da je X sigurno Hrvatica/Hrvat.” Opće je poznata činjenica da kada za neku osobu znamo da je Hrvatica/Hrvat, onda znamo i da je svako njezino/njegovo dijete također Hrvatica/Hrvat.

Englesku kraljevsku obitelj možemo zamisliti kao povezan usmjeren graf s $N$ čvorova gdje svaki čvor predstavlja jednog člana obitelji. Veza od čvora A do čvora B postoji ako je osoba koju predstavlja čvor $A$ roditelj osobi koju predstavlja čvor $B$. Znamo da u grafu postoji točno $N-1$ takvih veza.

Tvoj je zadatak nakon svakog novog saznanja s foruma o tome tko je Hrvatica/Hrvat, ispisati za koliko osoba sa sigurnošću možemo reći da su Hrvatice/Hrvati.

입력

U prvom su retku prirodni brojevi $N$ i $Q$ (1ドル ≤ N, Q ≤ 200,000円$).

U sljedećih $N-1$ redaka nalaze se prirodni brojevi $A$ i $B$ (1ドル ≤ A < B ≤ N$) koji predstavljaju vezu u grafu.

U sljedećih $Q$ redaka nalazi se prirodan broj $X$ (1ドル ≤ X ≤ N$), oznaka osobe za koju se sa sigurnošću saznalo da je Hrvatica/Hrvat.

출력

Ispiši $Q$ redaka. U $i$-ti redak ispiši za koliko osoba sigurno znamo da su Hrvatice/Hrvati nakon $i$-tog saznanja.

제한

힌트

Opis prvog primjera: Nakon što smo saznali da je osoba 3ドル$ Hrvat, samo za nju sa sigurnošću znamo da je Hrvat. Nakon toga saznajemo da je osoba 2ドル$ Hrvat, ali sada odmah i za njihovu djecu (3ドル$ i 4ドル$) znamo da su Hrvati, a nakon što znamo da je 4ドル$ Hrvat, odmah znamo i da je 6ドル$ Hrvat jer je dijete od 4ドル$. Na kraju saznajemo i da je osoba 5ドル$ Hrvat.