Pangaea 2

Time limit20sMemory limit256 MB

Summary

Starting from a given tree, each added road updates the minimum total length that keeps all cities connected, and each test case outputs the XOR of the answers.

Level: Hard8 of 10
Topics: Minimum spanning tree, Tree
Solved: No attempts yet

Problem

In the beginning the world had $n$ cities and $n - 1$ roads joining them. Each city carries an integer label between $0$ and $n - 1$ . Every road can be travelled in both directions and joins two different cities. In that first world you could walk from any city to every other city along one or more roads.

Humans gained wisdom and built a brilliant civilization, yet laying a new road between two cities was the one thing they never managed.

The creator watched this and began laying one road between two cities every year. The creator also wondered whether humans had the intelligence that the new roads deserve, so the creator posed this puzzle.

Every time a road is laid, choose some of the roads laid so far so that all cities are joined to each other directly or indirectly, and make the total length of the chosen roads as small as possible.

The humans who received the puzzle decided to solve it and show the creator that they deserve to use the roads. Nobody knows what a disappointed creator would do if they failed. You represent humankind, so you have to survive the trial the creator set.

Input

The first line contains the number of test cases $T$ . The first line of each test case contains the number of cities $n$ and the number of roads laid by the creator $m$ , separated by a space ( $1 \le n, m \le 100\,000$ ).

The next $n - 1$ lines describe the first world. Line $i$ ( $1 \le i \le n - 1$ ) contains two integers $u_i, c_i$ ( $0 \le u_i < i$ , $0 \le c_i \le 10\,000\,000$ ) separated by a space, which means city $i$ and city $u_i$ are joined by a road of length $c_i$ .

The next $m$ lines describe the roads the creator laid, in the order they were laid. Line $j$ ( $1 \le j \le m$ ) contains three integers $u_j, v_j, c_j$ ( $0 \le u_j, v_j < n$ , $0 \le c_j \le 10\,000\,000$ ) separated by spaces, which means the $j$ -th road the creator laid joins city $u_j$ and city $v_j$ and has length $c_j$ . $u_j$ and $v_j$ may be equal, and the road may join two cities that a road already joins.

Output

Print one line for each test case. The line contains the XOR of all $m$ answers, one answer for each road the creator laid.

Examples3

Example 1
Input
```
1
3 3
0 5
1 3
0 2 4
0 1 2
0 0 2
```
Expected output
```
7
```
Example 2
Input
```
1
1 1
0 0 0
```
Expected output
```
0
```
Example 3
Input
```
1
2 1
0 10
0 1 3
```
Expected output
```
3
```