{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e Read problems statements in \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/DEC15/mandarin/WAYPA.pdf\"\u003eMandarin Chinese\u003c/a\u003e, \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/DEC15/russian/WAYPA.pdf\"\u003eRussian\u003c/a\u003e and \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/DEC15/vietnamese/WAYPA.pdf\"\u003eVietnamese\u003c/a\u003e as well.\u003c/h3\u003e\r\n\r\n\r\n\u003cp\u003eSerega is an avid traveller. He has already visited numerous exotic places, and now wants to embark on a journey to Treeland. There are \u003cb\u003eN\u003c/b\u003e cities in Treeland that Serega wants to visit. Also, roads have been laid between some \u003cb\u003eN-1\u003c/b\u003e pairs of cities in Treeland. Roads are bidirectional, and there exists a unique path between any two Treeland cities.\r\n\u003c/p\u003e\r\n\u003cp\u003eEach of Treeland\u0027s roads has its own class, wich is specified using a single digit. Serega\u0027s 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.\r\n\u003c/p\u003e\r\n\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\nThe first line of input contains a single integer \u003cb\u003eT\u003c/b\u003e denoting the number of test cases. The description of \u003cb\u003eT\u003c/b\u003e test cases follows.\r\n\u003cp\u003eThe first line of each case contains a single integer \u003cb\u003eN\u003c/b\u003e. The next \u003cb\u003eN-1\u003c/b\u003e lines contain the roads. Each line contains three integers \u003cb\u003ev\u003c/b\u003e, \u003cb\u003eu\u003c/b\u003e and \u003cb\u003ec\u003c/b\u003e, meaning that there is a road of class \u003cb\u003ec\u003c/b\u003e between the \u003cb\u003ev\u003c/b\u003e\u003csup\u003eth\u003c/sup\u003e and \u003cb\u003eu\u003c/b\u003e\u003csup\u003eth\u003c/sup\u003e (assuming 1-indexing) cities of Treeland.\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each test case, you should output the maximum number of cities that Serega can visit.\u003c/p\u003e\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cb\u003e1 ≤ T ≤ 3*10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e1 ≤ N ≤ 10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003eSum of N over all test cases in a single file will not be greater then \u003cb\u003e3*10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e0 ≤ c ≤ 9\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e1 ≤ u, v ≤ N\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003eThe roads form a tree.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003ch3\u003eSubtasks\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003eSubtask #1 (15 points): \u003cb\u003e1 ≤ N ≤ 10\u003csup\u003e2\u003c/sup\u003e\u003c/b\u003e \u003c/li\u003e\r\n\u003cli\u003eSubtask #2: (85 points): \u003cb\u003e1 ≤ N ≤ 10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e \u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003e \u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n8\r\n1 2 1\r\n1 3 0\r\n3 4 1\r\n4 5 2\r\n1 6 0\r\n6 7 1\r\n7 8 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cp\u003eSequence of classes on the path between the cities \u003cb\u003e5\u003c/b\u003e and \u003cb\u003e8\u003c/b\u003e is \u003cb\u003e210012\u003c/b\u003e.\u003c/p\u003e"}}]}