Problem K
Alcohol-Free Alternative
In Sweden, across the Øresund Bridge, the alcohol laws are considerably harsher than in Denmark. Aside from the higher age limit, there are also a number of restrictions on how alcohol may be served. One of these restrictions concerns alcohol-free alternatives: a restaurant or bar with a license to serve alcohol must always offer an alcohol-free alternative.
A famous falafel restaurant in Malmö is currently composing a new menu, including recommended beverages. For each dish on the menu, the restaurant’s beer sommelier has picked one beer and one alcohol-free alternative that fits with the dish. If the restaurant had unlimited space in its beer cellar, they would have purchased both recommendations for every dish, but they are unfortunately severely limited in space.
The restaurant wants to offer a selection of beverages such that, for each dish, at least one of the sommelier’s two recommendations are included. To ensure that Danes would even care to cross the bridge and visit the restaurant, the selection must include at least one beer. Remember that the Swedish alcohol laws also require at least one of the alcohol-free alternatives to be included as well.
Can you find the smallest possible selection of beverages that fulfil these conditions?
Input
The first line contains a single integer $D$ ($1 \le D \le 40\, 000$) – the number of dishes on the menu.
The following $D$ lines contain the recommended beverages for each dish. Each line contains first the name of the beer, and then the name of the alcohol-free alternative.
There are at most $200$ distinct beers, and at most $200$ distinct alcohol-free alternatives. Each name consists of at most $20$ lower- and upper-case English letters. No beer shares the name with an alcohol-free alternative.
Output
First output a single integer $B$: the smallest size of a valid selection of beverages. Then output $B$ lines with the names of the beverages in a valid minimal selection, in any order. If there are multiple such selections you may answer with any one of them.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 Lagoonitas Cola Lagoonitas Water Lagoonitas Juice BrewCatRockIPA Juice |
2 Lagoonitas Juice |
| Sample Input 2 | Sample Output 2 |
|---|---|
1 YourBasicLager ShirleyTemple |
2 YourBasicLager ShirleyTemple |
| Sample Input 3 | Sample Output 3 |
|---|---|
5 Amstel AppleJuice Budweiser BitterLemon Carlsberg Citronil Duvel Danskvand Erdinger ElderflowerCordial |
5 Budweiser Carlsberg Duvel Erdinger AppleJuice |
