Wstęp do programowania w C++

Jasio ze swoją żoną Małgosią wybrał się na zakupy na świąteczny jarmark we Fraktalocji.

Fraktalocki jarmark ma specyficzną budowę. Składa się z n stanowisk połączonych n - 1 alejkami. Z każdego stanowiska do każdego innego można dotrzeć tylko jedną ścieżką. Jasio bardzo nie lubi robić zakupów, ale wie, że przedświąteczne zakupy są ważnym wydarzeniem dla jego żony Małgosi. Zatem, aby każde z nich było zadowolone, to przed rozpoczęciem zakupów, żona podaje numer stanowiska, od którego małżeństwo rozpoczyna robić zakupy, a Jasio określa tak trasę, aby odwiedzić możliwie najwięcej stanowisk oraz aby każde stanowisko odwiedzić tylko raz.

Niestety, Małgosia często zmienia zdanie odnośnie stanowiska początkowego, więc Jasio musi być przygotowany na taką ewentualność i mieć napisany program, który na podstawie planu Jarmarku wyznaczy długość możliwie najdłuższej trasy.

Wejście

W pierwszym wierszu znajduje się jedna liczba n ∈ [2, 10⁶] określająca liczbę stanowisk na fraktalockim jarmarku. W kolejnych n - 1 wierszach znajdują się opisy alejek.

Opis każdej alejki składa się z dwóch liczb a oraz b oznaczających, że stanowisko o numerze a łączy się ze stanowiskiem o numerze b bezpośrednią alejką (0 ≤ a, b < n).

W kolejnym wierszu znajduje się jedna liczba całkowita q ∈ [1, 10⁶] określająca liczbę zapytań.

Każde zapytanie składa się z jednej liczby całkowitej z (0 ≤ z < n) oznaczającej numer stanowiska, od którego małżeństwo będzie rozpoczynać robić zakupy.

Wyjście

Dla każdego zapytania wypisz w osobnej linii długość najdłuższej ścieżki rozpoczynającej się w podanym stanowisku.

Przykład

Wejście:

7
0 2
0 6
2 3
2 4
1 4
4 5
7
0
1
2
3
4
5
6

Wyjście:

4
5
3
4
4
5
5