该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“赛后递交”以递交本题。

题目描述

小Z作为房地产开发商代表，要对一个树形街道进行拆除，具体方式为每次选取一条还未被删除的道路（边）进行拆除，直到所有的道路均被拆除。

拆除的总成本计算方法如下，每次拆除一条道路的时候，计算这条边当前左右连接的住户数量，选取其中一个值，然后将每次选取的值都异或起来。

形式化地，当前的街道是一个树形结构，住户为节点、街道为边，最后的成本为 $cost$(初始化为 $0$)。每次删除一条还未被删除的边 $u-v$，选择此时的 $siz[u]$ 或 $siz[v]$，将其与 $cost$ 异或，即 $cost=cost\oplus siz[u]$ 或 $cost=cost\oplus siz[v]$。($siz[u]$ 表示当前 $u$ 所能连接的节点数量)

因为小Z作为包工头，需要最小化拆迁的总成本。求解这个最小成本，并给出一个符合这个最小成本的拆迁方式（任意方案均可）。

输入格式

第一行，$1$ 个正整数 $n$，表示住户总数量

接下来 $n-1$ 行，表示每条街道连接的 $2$ 个住户编号 $u,v$

输出格式

第一行，拆迁的最小总成本

接下来 $n-1$ 行，每行 $3$ 个数字 $u,v,x$，表示此时删除的边为 $u-v$，并且选择了 $siz[x]$ 作为异或的值

输入输出样例

2
1 2

1
1 2 1

样例 $\tt \#1$说明

删除边 $1-2$，选取 $siz[1]$，最后 $cost=1$，为最小结果

3
1 2
1 3

0
3 1 3
1 2 2

样例 $\tt \#2$说明

先删除边 $3-1$，并选取此时的 $siz[3]=1$，再删除边 $1-2$，并选取此时的 $siz[2]=1$，最后 $cost=1\oplus 1=0$ 为最小结果

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

0
2 5 5
1 3 1
4 2 2
1 2 1
5 6 5
5 7 7

数据范围

$2\le u,v\le n\le 10^5$