lucifer-traps-sam-and-dean-1

Lucifer traps Sam and Dean and locks them in Hell. To get out of Hell a pass key is required which was unknown to them. They found structure on a wall which contain N nodes which were connected to each other through N-1 edges such that there exist a path between any two nodes. Each pair of connection was assigned some weight.

Some other prisoners in hell told them that the pass key to get out is hidden in this structure. Prisoners told them that they need to find two distinct node U and V such that Xor-Sum of all weights present in the path of U to V is maximum. If more than one pair exists such that the Xor-Sum is maximum than U and V should be lexicographically smallest.

Formally, we say that a pair (U1, V1) is lexicographically smaller than another pair (U2, V2) if and only if :
1) U1 < U2 or
2) U1 = U2 and V1 < V2

Pass Key is the Xor-Sum of all the weights present in the path of U to V.

Xor-Sum of M numbers A1, A2, A3, ..., Am is (A1 xor (A2 xor (A3 xor ( .... (Am-1 xor Am)))..).

Help Sam and Dean to escape.

Input Format

First line of input contains integer N. Next N-1 lines contains 3 integers denoting U, V and W respectively where Uand V are the nodes in which edge exists and W is weight of the edge.

Output Format

In a first line output required Pass-Key.
In second line print all the nodes present in the path from U to V separated with a space.

Constraints

2 ≤ N ≤ 10^5
1 ≤ U, V ≤ N
0 ≤ W ≤ 10^9

Problem setter : Shiv Dhingra
Problem tester : Swapnil Saxena
SAMPLE INPUT
3
1 2 1
2 3 2

SAMPLE OUTPUT
3
1 2 3

Explanation

Since there are 3 nodes hence we can select two nodes in following way

(1,2) Xor-sum = 1
(2,3) Xor-sum = 2
(1,3) Xor-sum = 1 Xor 2 = 3
Hence maximum xor is 3 and path from node 1 to node 3 is 1 -> 2 -> 3.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: