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.|

AL_28_12 - Jaś, drzewo i dziwne pytanie

Jaś zaczął ostatnio czytać o teorii grafów. Podczas czytania wymyślił pewien problem, którego nie jest w stanie rozwiązać. Jesteś w stanie mu pomóc ?

Jest dane drzewo o N wierzchołkach. W każdy wierzchołek wpisana jest pewna unikalna liczba całkowita z przedziału [1, N]. Rozważ wszystkie proste ścieżki w tym grafie. Dla każdej prostej ścieżki można wypisać ciąg liczb z kolejnych wierzchołków na tej ścieżce. Dla każdego takiego ciągu można wypisać Najdłuższy rosnący podciąg tego ciągu. Znajdź najdłuższy z Najdłuższych rosnących podciągów ze wszystkich prostych ścieżek i wypisz jego długość.

Wejście

Wielkość każdego pliku wejściowego jest nie większa niż 2 MB.

W pierwszej linii wejścia znajduje się liczba zestawów danych T (1 ≤ T ≤ 1000).

W pierwszej linii każdego zestawu danych znajduje się jedna liczba całkowita N (1 ≤ N ≤ 105).

W każdej z kolejnych N - 1 linii zestawu danych znajdują się dwie liczby całkowite a i b (1 ≤ a, b ≤ N) oznaczające, że wierzchołek z wpisaną liczbą a jest połączony krawędzią z wierzchołkiem w który wpisana jest liczba b.

Wyjście

Dla każdego zestawu danych wypisz jedną liczbę, wynik dla problemu postawionego przez Jasia.

Przykład

Wejście:
2
12
3 1
1 4
4 12
12 8
4 5
5 11
5 6
5 2
3 9
9 10
9 7
12
1 8
8 6
8 3
3 12
3 10
3 5
5 4
5 2
1 9
9 11
9 7
Wyjście:
4
5
Jedno z rozwiązań dla drugiego testu:



Dodane przez:Bartek
Data dodania:2016-06-16
Limit czasu wykonania programu:2s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.