0213. Who is what

Имя входного файла:	c.in
Имя выходного файла:	c.out
Ограничение по времени:	2 s
Ограничение по памяти:	64 megabytes

John is a gamer. And I am a gamer. And there are millions of gamers all over the world and some of them compete at ACM during their free time┘ Free time from games of course :( Well, now seriously. John (not John Carmack) took part in the all-computer-games competition in year 2048 in Petrozavodsk and is probably now sitting on the same chair as you did in winter 2004 and surely desires victory as much as you did those cold days far away from your native city... At the opening which probably was at the same room as today▓s competitions opening he faced all other gamers. Some of them were Quakers, some liked StarCraft 3, some devoted themselves to Unreal Tournament 2048 but everyone loved only one game and the strangest thing was that there were no two gamers who liked the same game. Another strange thing was that some of them were not gamers at all, i.e. they did not play any game (probably jury agents but no one knows for sure what they do here). The competition was actually to prove that some game was better than other, that everyone who does not like Quake is lamer, that certain company ⌠sux■ while some other ⌠rulez■, etc┘, etc┘, etc┘ What John is really interested in is what kind of game every gamer prefers. To find that he has some useful information. He knows which game a particular gamer does not like. How does he know that? Well, a gamer devoted to first-person-shooters always wears some armor, even on the real street. So if John sees someone without loads of metal on his body, then he is definitely not Quaker, Counter Striker, etc┘ Also there are no Diablo 666 players without killed player ears necklace (with REAL ears on them). This set of rules can continue forever, John knows gamers community pretty well to see the difference. Another thing John strongly believes in is that only assignments providing the maximum number of gamers in the room among all possible assignments under given constraints can be the real assignment. Now the problem is, for every gamer given a list of games which do not contradict with his uniform, skin color, religion, etc┘ You are to find all those gamers for whom their beloved games are non-ambiguous from this information.

Input file

The first line contains two numbers: N and M, the number of gamers and number of games at the competition correspondingly. 0 ≤ N, M ≤ 32. Then follows the list of pairs P Q, 1 ≤ P ≤ N, 1 ≤ Q ≤ M. P denotes a gamer and Q denotes a game which he probably plays all his life. A line ⌠0 0■ (without quotes) terminates the input and has no other meaning. By default a particular gamer does not play a particular game, e.g. if there is no line 2 3, then gamer 2 does not play game 3. If such line exists, then player 2 either plays game 3 or plays some another game enlisted for his ID or he is not a gamer at all.

Output file

List all gamers for whom assignment to their favorite games is unambiguous. Please do not list non-gamers; they will be publicly executed anyway once everyone knows this weird fact about them. Each line of the output should be in the form P Q with the same meaning as in the input. If there are no gamers with unambiguous game assignment, please save some bytes of our free HDD space by keeping the output empty.

Example:

c.in	c.out
5 5 1 2 2 1 2 3 4 4 3 1 3 3 0 0	1 2 4 4

Источник: Petrozavodsk Winter 2004. Denis Koshman Contest, Saturday, January 31
Автор: Denis Koshman

Обсудить       Отправить решение



Версия для печати