Description
Problem Description
Task.
You’re planning a company party. You’d like to invite as many people as possible with a single constraint: No person should attend a party with his or her direct boss.
Find out what is the maximum possible number of invited people.
Print all the invited employees.
Input Format.
The 1st line contains an integer n: the number of people in the company.
Each of the next n − 1 lines describes the subordination structure. Everyone but for the CEO of the company has exactly 1 direct boss. There are no cycles: nobody can be a boss of a boss of a ... of a boss of himself. So, the subordination structure is a regular tree. Each of the n − 1 lines contains two integers u and v, and
you know that either u is the boss of v or vice versa (you don’t really need to know which one is the boss, but you can invite only one of them or none of them).
E.g. 1.:
Input:
1
Output:
1
1
E.g. 2.:
Input:
2
1 2
Output:
1
2
E.g. 3.:
Input:
5
5 4
2 3
4 2
1 2
Output:
3
1 3 5
E.g. 4.:
Input:
8
1 2
1 3
2 4
2 5
3 6
5 7
5 8
Output:
5
1 4 6 7 8