Eșuând în a-și regăsi adevărata identitate, Brush se refugiază în magicul tărâm al arborilor. Arbotra o sună și îi dă următoarea problemă: se dă un arbore cu N noduri, o rădăcină fixată, și M întrebări de forma: câte perechi neordonate de noduri pot forma, luând noduri doar din subarborele nodului X (inclusiv pe X).

Cerința

Ajutați-o pe Brush să răspundă cât mai repede la intrebările lui Arbotra.

Date de intrare

Fișierul de intrare arbrush.in va conține pe prima linie trei numere naturale, numărul N, M și Root, separate de un spațiu. Următoarele N-1 linii vor conține două numere naturale a și b (între 1 și N), separate de un spațiu, cu semnificația că există muchie între nodurile a și b. Ultima linie a fișierului de intrare (linia N+1) va conține M numere separate de căte un spațiu, acestea vor semnifica cele M întrebari cerute de Arbotra.

Date de ieșire

Fișierul de ieșire arbrush.out va conține M linii, aflându-se răspunsul la fiecare întrebare cerută (în ordinea cerută în fișierul de intrare).

Restricții și precizări

• 2 ≤ N, M ≤ 27040
• 1 ≤ Root ≤ N
• Uituc de fel, Arbotra poate pune aceeași întrebare de mai multe ori.

Exemplu:

arbrush.in

8 4 1
1 2
2 3
2 5
5 6
6 7
6 8
1 4
6 4 5 2

arbrush.out

3
0
6
15

Explicație

Pentru prima întrebare, răspunsul este 3, deoarece în subarborele nodului 6 există 3 noduri: 6, 7, 8, cu care pot forma perechile {6, 7}, {7, 8}, {6, 8}

Pentru a doua întrebare răspunsul este 0, deoarece subarborele lui 4 are doar un nod, pe el înșusi și nu se pot forma perechi de câte două noduri.

Pentru a treia întrebare răspunsul este 6, deoarece în subarborele nodului 5 există 4 noduri: 5, 6, 7, 8, perechile formate sunt {6, 8}, {5, 6}, {7, 8}, {5, 8}, {5, 7}, {6, 7}

Pentru a patra întrebare răspunsul este 15.