Mr. W got a new graph with N vertices and N - 1 edges. It's a connected graph without cycles. Each edge should have an ugly value. To make the graph more beautiful, Mr. W hope you can help him modify it. You can delete or add one edge with an ugly value at a time and you can do it as many times as you want. But the following conditions should be satisfied at any time:

1. The graph is connected.

2. For each cycles in the graph, the XOR sum of all ugly values in the cycle is 0.

Mr. W wants to know the minimum sum of ugly values of all edges in the graph.