Gift Exchange
Time limit2sMemory limit128 MB
Given a functional graph where each of N students names two chosen recipients, select the largest subset of students such that every selected student receives exactly two gifts from other selected students.
- Level
Medium7 of 10
- Topics
- Graph, Greedy, Implementation
- Solved
- No attempts yet
Problem
A gift exchange will be held on the last day of camp. Each student gives gifts to two predetermined friends.
If the event is run as-is, some students may receive no gift or only one gift, while others may receive three or more. The organizers therefore want to choose only some students so that every participating student receives exactly two gifts.
For each student, the two students they want to give gifts to are given. Write a program that chooses as many participating students as possible.
Input
The first line contains the number of students N (3 <= N <= 200,000). The students are numbered from 1 to N.
Each of the next N lines contains two distinct student numbers, separated by a space: the two students that student i wants to give gifts to. A student never gives a gift to themself.
Output
On the first line, print the maximum number of students who can participate.
If at least one student participates, print the participating students' numbers in increasing order on the second line, separated by spaces. If there is more than one valid answer, print any one of them.
If no student can participate, print only 0 on the first line.