Chiaki has a rooted tree with n nodes numbered 1 to n. The root is node 1. Each edge has a positive integer weight on it.
Now, two players are playing a game on the tree. They play the game in turn. In each turn, the player should choose an edge and decrease its weight by 1.
If an edge's weight becomes 0, it will be removed. After an edge is removed, the tree will be split into two parts. The part without the root node should be discarded (i.e. permanently removed from the tree).
If in a turn, a player has no edge left to choose, he loses the game.
Chiaki, as the player with the first turn, would like to know which edges she can choose at the first turn, to make sure she will win?
输入描述:
There are multiple test cases. The first line of the input contains an integer T, indicating the number of test cases. For each test case:
The first line contains an integer n (1 ≤ n ≤ 106) -- the number of nodes in the tree.
Each of the next n-1 lines contains two integers pi and wi (2 ≤ i ≤ n, 1 ≤ pi ≤ n, 1 ≤ wi ≤ 109) where pi denotes the parent of the i-th node and wi is the weight of the edge between i and pi.
It's guaranteed that the sum of n in all test cases will not exceed 106.
输出描述:
For each test case, output two lines.
The first line is a single number m, the number of edges Chiaki can choose at the first move to make sure Chiaki will win.
The second line contains m increasing numbers separated with one space. Output the number u means you can choose the edge between node u and its parent.
示例1
输入
复制
3
5
1 2
1 2
1 2
1 1
5
1 2
1 2
1 2
1 2
5
1 1
2 1
3 1
4 1