#P17958. Maximum Mex

Maximum Mex

Maximum Mex

题目描述

给定一棵有 nn 个结点的树。每条边 (ui,vi)(u_i,v_i) 上写有一个非负整数 aia_i,且每个数值至多出现在六条边上。

对于任意两个结点 u,vu,v,考虑它们之间唯一简单路径上的全部边权。定义这条路径的价值为这些边权的 mex,即没有在路径上出现的最小非负整数。

求所有结点对对应的路径价值的最大值。

输入格式

第一行一个整数 tt,表示测试用例数,1≤t≤1041\le t\le10^4。

每组测试用例的第一行包含一个整数 nn,3≤n≤1053\le n\le10^5。

接下来 n−1n-1 行,每行三个整数 ui,vi,aiu_i,v_i,a_i,表示一条边及其边权,满足 1≤ui,vi≤n1\le u_i,v_i\le n、ui≠viu_i\ne v_i、0≤ai<n0\le a_i<n。

保证给出的边构成一棵树,且每一种边权在该测试用例中出现的次数不超过六次。

所有测试用例的 nn 之和不超过 10510^5。

输出格式

每组测试用例输出一行一个整数,表示路径价值的最大值。

样例 1

输入

3
4
2 1 0
1 3 1
1 4 2
5
1 2 0
1 3 1
2 4 0
2 5 2
10
2 3 0
6 10 1
3 7 2
10 9 0
8 2 0
1 9 2
5 2 1
9 3 2
4 10 3

输出

2
3
4