You are given a tree with $n$ nodes (conveniently numbered from $1$ to $n$). Each edge in this tree has one of $n$ colors. A path in this tree is called a *rainbow* if all adjacent edges in the path have different colors. Also, a node is called *good* if every simple path with that node as one of its endpoints is a *rainbow* path. Find all the *good* nodes in the given tree. A simple path is a path that does not repeat any vertex or edge.

The first line of input contains a single integer $n$ $(1 \le n \le 50,000)$. Each of the next $n - 1$ lines contains three space-separated integers $a_i$, $b_i$, and $c_i$ $(1 \le a_i, b_i, c_i \le n;\ a_i \ne b_i)$, describing an edge of color $c_i$ that connects nodes $a_i$ and $b_i$. It is guaranteed that the given edges form a tree.

On the first line of the output, print $k$, the number of good nodes. In the next $k$ lines, print the indices of all good nodes in numerical order, one per line.

For the first sample, node $3$ is good since all paths that have node $3$ as an endpoint are rainbow. In particular, even though the path $3\rightarrow 4\rightarrow 5\rightarrow 6$ has two edges of the same color $(\text{i.e. }3\rightarrow 4, 5\rightarrow 6)$, it is still rainbow since these edges are not adjacent.

2017 Pacific Northwest Region Programming Contest