Trip and Palindromes

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Serega is an avid traveller. He has already visited numerous exotic places, and now wants to embark on a journey to Treeland. There are N cities in Treeland that Serega wants to visit. Also, roads have been laid between some N1 pairs of cities in Treeland. Roads are bidirectional, and there exists a unique path between any two Treeland cities.
Each of Treeland's roads has its own class, wich is specified using a single digit. Serega's journey is a path between some cities, i.e. he never visits one city more than once. But Serega wants to select a path such that the sequence of classes on the path is a palindrome. Of course, Serega wants to visit as many cities as possible. Please help Him.
Input
The first line of input contains a single integer T denoting the number of test cases. The description of T test cases follows.The first line of each case contains a single integer N. The next N1 lines contain the roads. Each line contains three integers v, u and c, meaning that there is a road of class c between the v^{th} and u^{th} (assuming 1indexing) cities of Treeland.
Output
For each test case, you should output the maximum number of cities that Serega can visit.
Constraints
 1 ≤ T ≤ 3*10^{5}
 1 ≤ N ≤ 10^{5}
 Sum of N over all test cases in a single file will not be greater then 3*10^{5}
 0 ≤ c ≤ 9
 1 ≤ u, v ≤ N
 The roads form a tree.
Subtasks
 Subtask #1 (15 points): 1 ≤ N ≤ 10^{2}
 Subtask #2: (85 points): 1 ≤ N ≤ 10^{5}
Example
Input: 1 8 1 2 1 1 3 0 3 4 1 4 5 2 1 6 0 6 7 1 7 8 2 Output: 7
Explanation
Sequence of classes on the path between the cities 5 and 8 is 210012.
Author:  gomelfk 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/WAYPA 
Tags  binarysearch centroiddecomp dec15 gomelfk hard hashing 
Date Added:  1112015 
Time Limit:  5 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 