Hide

# Problem DOrangestone Network

Sensing an opportunity, you decide to become a telecommunications mogul by connecting $n$ villages with orangestone links. To save costs, you use the minimum number of links required to connect all $n$ of the villages, and since lag would be unbearable otherwise, any two villages are connected by a path of at most $100$ links.

Unlike redstone, orangestone links can be turned on and off, but only in the following way: in one move, you may select a village all of whose links to other villages are off and turn them all on, or you may select a village all of whose links to other villages are on and turn them all off.

Your friends who were helping you build the network messed it up and now some of the links are off! Now you need to figure out a sequence of moves to turn all of the links on. As you need to move quickly before competitors show up, you can take at most $50n$ moves to turn the network on.

## Input

The first line of input contains one integer $n$, $2 \leq n \leq 10^4$, the number of villages. The villages are numbered from $1$ to $n$.

The next $n-1$ lines each contain three space-separated integers $a_ i,b_ i,s_ i$, $1 \leq a_ i, b_ i \leq n$ and $s_ i\in \{ 0,1\}$. Each line represents a link between $a_ i$ and $b_ i$. If $s_ i=0$ then the link is off, while if $s_ i=1$ the link is on.

## Output

On the first line of output, print one integer $m$, $0 \leq m \leq 50n$, the number of moves you need to turn all the links on.

On the $i$th of each of the following $m$ lines, print one integer $a_ i$, indicating that your $i$th move is to flip all of the links adjacent to village $a_ i$.

It can be shown that a valid sequence of at most $50n$ moves exists for any input satisfying the above constraints.

Sample Input 1 Sample Output 1
3
2 1 0
3 1 0

2
2
3

Sample Input 2 Sample Output 2
10
10 5 0
3 9 0
9 7 0
3 2 1
4 5 1
1 7 1
7 10 0
8 7 1
6 2 1

6
2
4
9
2
10
4

Sample Input 3 Sample Output 3
10
10 3 0
8 1 0
1 2 1
4 8 1
7 5 1
4 9 0
6 5 0
6 10 1
2 7 0

13
9
4
3
10
6
3
5
10
7
6
3
8
9