瓦莱拉居住的城市即将举行市议会选举。
该市有n个区和n-1条双向道路。我们知道,从任何一个地区都有一条通往其他地区的道路。让我们用 1 到 n(含)的整数以某种方式枚举所有地区。此外,对于每条道路,居民都会决定它是否是问题道路。有问题的道路是需要修理的道路。
有 n 位候选人参加选举。让我们用 1 到 n 之间的整数以某种方式枚举所有候选者。如果第 i 号候选人当选市议会,他将履行一个承诺——修复从第 i 区到市议会所在 1 区途中的所有问题道路。
帮助 Valera 确定候选人子集,如果该子集中的所有候选人都当选为市议会成员,则该市所有有问题的道路都将得到修复。如果有多个这样的子集,您应该选择由最少数量的候选者组成的子集。
输入
第一行包含一个整数 n (2 ≤ n ≤ 105) — 城市中的区数。
接下来是 n - 1 行。每行包含对城市道路的描述,用三个正整数 xi、yi、ti (1 ≤ xi, yi ≤ n, 1 ≤ ti ≤ 2) — 第 i 条双向道路和道路类型连接的区域。如果ti等于1,则第i条路不是问题路;如果ti等于2,则第i条路是问题路。
保证城市的图结构是一棵树。
输出
在第一行中打印一个非负数 k — 所需候选子集的最小大小。然后在第二行打印 k 个空格分隔的整数 a1, a2, ... ak — 构成所需子集的候选数。如果有多个解决方案,您可以打印其中任何一个。
示例
输入 #1
5 1 2 2 2 3 2 3 4 2 4 5 2
输出 #1
1 5
输入 #2
5 1 2 1 2 3 2 2 4 1 4 5 1
输出 #2
1 3
输入 #3
5 1 2 2 1 3 2 1 4 2 1 5 2
输出 #3
4 5 4 3 2