AlgoLiga 2018

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 ≤ 10⁵).

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: