tree

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

There is a tree(the tree is a connected graph which contains $n$ points and $n-1$ edges),the points are labeled from 1 to $n$,which edge has a weight from 0 to 1,for every point $i\in[1,n]$,you should find the number of the points which are closest to it,the clostest points can contain $i$ itself.

Input

the first line contains a number T,means T test cases.

for each test case,the first line is a nubmer $n$,means the number of the points,next n-1 lines,each line contains three numbers $u,v,w$,which shows an edge and its weight.

$T\le 50,n\le 10^5,u,v\in[1,n],w\in[0,1]$

Output

for each test case,you need to print the answer to each point.

in consideration of the large output,imagine $ans_i$ is the answer to point $i$,you only need to output,$ans_1~xor~ans_2~xor~ans_3..~ans_n$.

Sample Input

1 3 1 2 0 2 3 1

Sample Output

1 in the sample. $ans_1=2$ $ans_2=2$ $ans_3=1$ $2~xor~2~xor~1=1$,so you need to output 1.

Hint

hujie

Source

BestCoder Round #68 (div.2)

提交代码