Association of Cyber cafe Managers (ACM) has recently discovered that the cyber cafes have not been placed in proper places of the cities. Some parts of the cities have many of them, while some important parts have none. ACM is now planning to setup one cyber cafe in each important part of large cities. Each of the new cyber cafes will have one server connected to several terminals. As the number of cyber cafes is now increasing, ACM has bought some new servers. The cyber cafes that will be equipped with new servers will be called grade A cy- ber cafes, and the rest which contains the old servers will be called grade B cyber cafes. Although the old servers are quite good, there is a chance that people will try to avoid grade B cyber cafes and prefer grade A ones if they have that opportunity. If someone finds that the nearest cyber cafe is of grade B and there are more than one grade A cyber cafes within 1 km distance, he/she will never use the grade B cyber cafe. As a result, that cyber cafe will not get enough customers to support itself. If there is only one grade A cyber cafe near (within one km) a grade B cyber cafe then people will still use the grade B cyber cafe because the only neighboring grade A cyber cafe may be filled with people. So, ACM is planning to build grade A and grade B cyber cafes in such a way that no grade B cyber cafe is within 1 km distance of two or more grade A cyber cafes. ACM has already rented one building for each cyber cafe. The rented buildings of a city have been marked with single uppercase letters for identification. ACM has also decided how many new servers should be allotted to each city. Now, it is time to place the servers in the cyber cafes. Given all the pairs of buildings that are within 1 km distance of each other, your job is to find out the possible ways of placing the servers meeting the above criterion. All the new servers are similar. The old ones are also similar. All cyber cafes should have exactly one server. For examples if there are five cyber cafes and two new servers then three (5 − 2 = 3) old servers will be required.
2/2 Input Input consists of less than 60 (Sixty) datasets. Each dataset consists of the followings: • A line containing the name of the city (which has 2 to 16 alphanumeric characters). • A line containing 3 positive integers n, s and p denoting respectively the number of buildings, the number of new servers and the number of building pairs that are within 1 km from each other (0 < s < n < 17). The integers are separated by exactly one space. The n buildings are marked with ‘A’, ‘B’, etc. in that order. • Next line contains p pairs of uppercase letters. Each pair indicates that the corresponding build- ings are within 1 km of each other. One pair is separated from the next with exactly one space. The end of input is marked with a line consisting of ‘TheEnd’. Output For each set, print 2 lines. The first line should contain the name of the city. The next line should contain the number of possible ways to place the servers. The last line of output should be a line consisting of the string ‘TheEnd’ (without the quotes). Sample Input Dhaka 627 AB BC CD DE EF FA AD Chittagong 434 AB AC AD BC Sylhet 323 AB BC CA TheEnd Sample Output Dhaka 9 Chittagong 1 Sylhet 0 TheEnd