The Transit Authority of Greater Podunk is planning its
holiday decorations. They want to create an illuminated display
of their light rail map in which each stretch of track between
stations can be illuminated in one of several colors.
At periodic intervals, the controlling software will choose
two stations at random and illuminate all of the segments
connecting those two stations. By design, for any two stations
on the Greater Podunk Railway, there is a unique path
connecting the two.
For maximum color and cheer, the display designers want to
avoid having two adjacent segments of track lighting up in the
same color. They fear, however, that they may have lost track
of this guideline in the process of building the display. One
of them has gone so far as to propose a means of measuring just
how far from that ideal they may have fallen.
Description
You are given a tree with $n$ nodes (stations), 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. (A simple path
is a path that does not repeat any vertex or edge.)
Find all the good nodes in the given tree.
Input
The first line of input contains a single integer
$n$ ($1 \le n \le 50\, 000$).
Each of the next $n1$
lines contains three spaceseparated 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.
Output
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.
Examples
(For the first sample, node $3$ is good because 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 (i.e.
$3 \rightarrow 4$,
$5 \rightarrow 6$), it is
still rainbow because these edges are not adjacent.)
Sample Input 1 
Sample Output 1 
8
1 3 1
2 3 1
3 4 3
4 5 4
5 6 3
6 7 2
6 8 2

4
3
4
5
6

Sample Input 2 
Sample Output 2 
8
1 2 2
1 3 1
2 4 3
2 7 1
3 5 2
5 6 2
7 8 1

0

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

5
1
2
3
6
7

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

4
1
6
7
9
