Tom was empolyed by the world’s most famous Map Publishing Press. They do the boring work of painting the maps. Assign limited color to different countries without adjacent countries share the same color. Despite the mathematicians have proved that four color is enough, finding out a proper 4-color solution in limited time for some map with great complexity is almost impossible. So they are allowed to use five color: Blue, Green, Pink, Red and Yellow. Although it is not very difficult now, Tom want to be completely free from this task. He want a computer to do this for him. But the problem is that he knows nothing about programing, then he ask you for help. Your task is to write a program which generate proper solution correspoding to each map description. Input The input contains several map descriptions. Each description have a ‘#’ at the end. In each description, there are arbitary number of lines. Each line consists of two parts: the first part is a single string which denotes a country; the second part consists of several strings denoting a list of its adjacent countries. i.e : China Mongolia Russia This line says that China is neighboured by Mongolia and Russia. You should choose proper color for each country. No adjacent countries should have same color. There is an ‘END’ at the end of the input file. Note: The name of countries consists of up to 20 characters without seperating spaces. There will be up to 500 countries in each description and no country named ‘END’. countries are seperated from another by one or more spaces. Output For each map in the input, first print the number of the map, as shown in the sample output, followed by your solution. One line for each country, consists of the name of the country and the color you selected. Multiple lines should be sorted in lexicographical order. Any solution satisfied the above requirement is acceptable. If there are no possible solution, print ‘Impossible’. Output a blank line after each test cases. Sample Input China Mongolia Russia Russia Mongolia
END Sample Output Map #1 China Red Mongolia Green Russia Pink