Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3738
Buy the Pets

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(1iN) represent the ith people, use i(N+1iN+M) represent the (i-N)th cat, use i(N+M+1iN+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.


One line for each test case. The number of reasonable ways.

Sample Input

1 2 2
2 4
3 5
2 2 2

Sample Output


Author: CHEN, Zemin
Contest: ZOJ Monthly, December 2013
Submit    Status