Time Limit: 2 Seconds
Memory Limit: 65536 KB
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.
Input 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 ith people, use i(N+1≤ i≤ N+M) represent the (i-N)th cat, use i(N+M+1≤ i≤ N+M+P) represent the (i-N-M)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.