## Mock CCC '18 Contest 2 S4 - A Tree Problem

View as PDF

Points: 12 (partial)
Time limit: 0.6s
Java 1.0s
Memory limit: 1G

Problem type

You are given an undirected tree of vertices. Every edge in the tree has a color. A path is good if every adjacent pair of edges in the path have different colors. A vertex is good if every simple path starting at that vertex and ending somewhere else in the tree is good.

Compute all good nodes.

#### Constraints

for all

In tests worth 5 marks, .

#### Input Specification

The first line contains a single integer .

Each of the next lines contains three space-separated integers, , , and , denoting an edge of color connecting vertices and .

#### Output Specification

On the first line, print , the number of good vertices.

For each of the next lines, print the ID of a good vertex. The lines must be printed in sorted order.

#### Sample Input 1

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

#### Sample Output 1

4
3
4
5
6

#### Sample Input 2

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

#### Sample Output 2

0

#### Sample Input 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

#### Sample Output 3

5
1
2
3
6
7

#### Sample Input 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

#### Sample Output 4

4
1
6
7
9