Picture by user Acdx via Wikimedia Commons
A friend of yours works at an undisclosed company in the
music streaming industry, and needs your help. The company has
offices in Stockholm and London, and collaboration between the
two offices is extensive. The situation is that each of the
many but small projects are handled by a two-person team with a
member in each city. While emails, faxes, and phones are
wonderful, and work well within each team, the CEO wants a
briefing every year on the projects. For this purpose the CEO
invites representatives from the projects to Barbados for a
week of
beach fun presentations of all the projects.
However, money is tight and a new policy has been created:
the CEO wants at least one person from each project, and
additionally, she wants to invite as few people as possible.
This is where you come in. In order to help your friend get a
ticket to Barbados, you are to write a program that, given all
the two-person teams, computes the smallest number of people
that must be invited in order to get at least one person from
each project, as well as a list of people to invite. If
possible (subject to the set of people being smallest
possible), the list of invitees should include your friend.
Input
The first line of input contains an integer , the number of
teams. The following
lines each contain two integers, separated by a space, being the
employee IDs of the two employees in that team (the first one
is from Stockholm and the second one is from London). Stockholm
employees have IDs in the range to and London employees have IDs
in the range to
. An employee can be
a member of several teams, but there cannot be several teams
consisting of the same pair of employees. Your friend has ID
.
Output
Output first a single line with an integer indicating the smallest number of
employees that must be invited to meet the requirements above.
Then output lines
giving the IDs of employees to invite. If possible (subject to
being smallest
possible), the list should contain your friend.
If there are several solutions subject to these constraints,
anyone is acceptable.
| Sample Input 1 |
Sample Output 1 |
2
1009 2011
1017 2011
|
1
2011
|
| Sample Input 2 |
Sample Output 2 |
4
1009 2000
1009 2001
1002 2002
1003 2002
|
2
2002
1009
|
