题目描述

这，就是我们的故事。

给定一棵包含 $n$ 个顶点的树，顶点编号为 $1,2,\dots,n$。每条边 $(u,v)$ 有一个非负整数权值 $w(u,v)$。

定义树上的一条途径为一个顶点序列 $v_1, v_2, \dots, v_k$（$k \ge 1$），满足对于任意的 $i$（$1\le i\le k-1$），都有一条边 $(v_i,v_{i+1})$。请注意，途径中的顶点可以重复，即如果存在 $1\le i< j\le k$ 满足 $v_i=v_j$，仍然认为这是一条途径。

途径的边数定义为 $k-1$，即途径经过的边的数量。

途径经过的顶点集定义为 $\{v_1, v_2, \dots, v_k\}$，即途径中所有出现过的顶点（重复只计一次）。

途径的代价定义为沿途经过的边的权值的异或和：$w(v_1, v_2)\oplus w(v_2, v_3)\oplus w(v_3, v_4)\oplus\cdots\oplus w(v_{k-1},v_k)$，其中 $\oplus$ 表示按位异或。特别地，当 $k=1$ 时（即途径只包含一个顶点），途径的代价为 $0$。

要求选择一条途径，满足如下条件：

• 它经过树中所有的顶点，即途径经过的顶点集等于全部 $n$ 个顶点；
• 在所有满足条件 1 的途径中，途径的代价最小；
• 如果有多条途径同时满足条件 1 和 2，则选择途径的边数最少的；
• 如果有多条途径同时满足条件 1、2 和 3，则选择任意一条，都会被视为正确。

输出一条满足上述条件的途径，以顶点序列的形式给出。

输入格式

输入的第一行，包含一个整数 $n$（$1 \le n \le 5 \times 10^5$），表示给定的树有 $n$ 个顶点。

接下来 $n-1$ 行，每行包含三个整数 $u,v$ 和 $w$（$1\le u,v\le n, 0\le w<2^{30}$），表示树上存在一条边 $(u,v)$，边权为 $w$。保证给出的边构成一棵树。

输出格式

输出两行。第一行包含一个整数 $k$（$1 \le k \le 4 \times 10^6$），表示途径的顶点序列的长度。

第二行包含 $k$ 个整数 $v_1, v_2, \dots, v_k$，用一个空格分隔，表示一条满足条件的途径，其顶点序列为 $v_1, v_2, \dots, v_k$。

可以证明，在题目的约束下：

• 所有顶点的编号都需要至少出现一次；
• 对于任意一条满足题目条件 1、2 和 3 的途径，其顶点序列的长度均不超过 $4 \times 10^6$。

4
1 2 0
1 3 2
3 4 2

4
4 3 1 2

6
1 2 1
3 6 5
3 1 2
2 5 3
4 2 4

8
3 6 3 1 2 4 2 5