To_be_xor_not_to_be (RMI contest)
Time limit: 1 seconds | Memory limit: 512 MB | Task type: batch
Algorithms: dynamic programming, trie, bitmask, tree

# To be, xor not to be

Time limit: *1000 ms*
Memory limit: *512 MB*

The noble Stegan, a prince of Dendromark, was left with sorrow by passing of his beloved father. After tiresome and useless struggles to find out what fate his father met by computing the area of various trapezoid figures using Simpson's rule, when all hope was lost, a spirit came to his aid. And the spirit gave him a **tree** to harness and take into his care. And the spirit later told him: *Look! Look closer! Do you see? This tree is special as it has an even number of vertices. Should you be able to find the best manner in which to pair these vertices so that the total cost of this pairing is as small as possible, you shall find how the passing of you father came to be. But first you shall figure out what is the cost of a pairing; its secret lies in the meaning of life.*

Stegan, a great mathematician that he happens to be, knows that the true meaning of life can be found in the words: "To be **xor** not to be" (and in the lines that followed it, but that is of no concern to us). Therefore he deduced that, for a pair of vertices, the cost of their pairing is the bitwise xor of the weights of the edges that lie on the simple path that connects the two vertices.

Unfortunately, providence has not gifted Stegan with computer science skills and so he has not a clue how to come by the solution to his problem and he has come to you to beg for help.

Formally, you are given a **tree** with N vertices, where N is even. Every edge has a weight. For a pair of vertices (u, v) we define the cost to pair them up to be the bitwise xor of the weights of the edges that lie on the simple path that connects the two vertices.

You have to find a way to split the vertices into N / 2 pairs such that the total sum of their costs is as small as possible. Because it might be too hard to ask you to find the actual minimum solution, we only ask you to do your best and you will receive points accordingly.

## Standard input

The first line of the input contains an even integer, N — the number of vertices in the tree. Each of the next N - 1 lines will consist of 3 space-separated numbers `u_i, v_i, w_i` meaning that there is an edge of weight `w_i` that connects `u_i` and `v_i`. Both `u_i` and `v_i` are between 1 and N. Vertices are 1-indexed.

## Standard output

On the first line, you should print the total cost of the pairs of vertices you have chosen. On the next N/2 lines, on each line you should print the indexes (1 to N) of two nodes that should be paired together. Each node must appear in exactly one pair.

## Scoring

This is an approximate problem. For each group of tests:

1.  If there is a test case for which your program doesn't generate a valid response (e.g., Time Limit Exceeded, Runtime Error, incorrect output format) then you will receive 0 points for that group.
2.  A response is also considered invalid if the N/2 pairs that you output do not form a valid partition of the N nodes (i.e., each node is not in exactly one pair) or if the reported total cost does not match the sum of the costs of the pairs you output.
3.  If your output is valid for all test cases in a group, your score for that group is calculated based on the formula:

    `Score = group_points * min over all tests i in the group { (optimal_cost_i / your_cost_i) ^ 4 }`

    where:
    * `i` identifies a specific test case within the group.
    * `your_cost_i` is the total cost your solution computed for test case `i`.
    * `optimal_cost_i` is the pre-calculated minimum possible cost for test case `i`.
    * `group_points` is the total points allocated to the group.
    * Note: If `your_cost_i` is 0 and `optimal_cost_i` is also 0, the ratio is 1. If `your_cost_i` is 0 and `optimal_cost_i` > 0, the ratio is considered infinity, and the score for the group will be 0.

## Constraints and notes

* 2 <= N <= 200
* N is even
* 0 <= `w_i` < 2^24 (Edge weights are non-negative integers less than 16,777,216)

| # | Points | Restrictions       |
|---|--------|--------------------|
| 1 | 3      | N <= 10 and `w_i` < 64 |
| 2 | 6      | N <= 14            |
| 3 | 19     | N <= 40 and `w_i` < 64 |
| 4 | 8      | N <= 120 and `w_i` < 16 |
| 5 | 41     | N <= 120           |
| 6 | 23     | No further restrictions |

---

**Example 1:**

*Input:*
```
6
5 2 42
5 4 52
6 3 26
4 6 39
1 6 15
```
*Output:*
```
54
1 6
3 5
4 2
```

---

**Example 2:**

*Input:*
```
4
1 2 4
3 4 5
2 3 1
```
*Output:*
```
1
2 3
1 4
```

---


Starter code:

Grader code:

Setup script:

Evaluation script: