Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_16__20 - Jarmark świąteczny

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, 106] 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, 106] 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

Dodane przez:Marcin Kasprowicz
Data dodania:2022-12-16
Limit czasu wykonania programu:5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM32-GCC COBOL D-CLANG D-DMD ELIXIR FANTOM GOSU GRV JS-MONKEY NIM OBJC OBJC-CLANG PICO RUST SCM qobi CHICKEN VB.NET

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.