
ZOJ Problem Set  3738
Dogs and Cats are human's friends. But as we all know, when dog and cat live together, they might fight. One day, N people go to the pet shop to buy the pets. They all want to buy one cat and one dog. But some people might be allergic to some cats. Now the problem comes, how many different reasonable ways can make all the people satisfied. A reasonable way satisfies that the cat and the dog which belong to the same people will not fight and the master is not allergic to his cat. InputInput will consist of multiple test cases. The first line of each case consists of three integers N, M, P(1≤ N, M, P≤ 10). N is the number of people, M is the number of cats, P is the number of dogs. Notice that we use i(1≤ i≤ N) represent the i^{th} people, use i(N+1≤ i≤ N+M) represent the (iN)^{th} cat, use i(N+M+1≤ i≤ N+M+P) represent the (iNM)^{th} dog. The next line contains an integer Q implies we will give you Q relationships. In the next Q lines, each line contains two integer x and y, means x and y can't live together. OutputOne line for each test case. The number of reasonable ways. Sample Input1 2 2 2 2 4 3 5 2 2 2 0 Sample Output2 4 Author: CHEN, Zemin Contest: ZOJ Monthly, December 2013 