D. Dealing with São Paulo Hot Dogs
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The city of São Paulo is known for having great hot dog snacks. Ernesto is one of the owners of a very famous hot dog trailer in the area. To make a quality hot dog, he follows some rules:

  • Exactly one type of bread and one type of sausage must be used.
  • It is not allowed to simultaneously include two ingredients that Ernesto believes do not mix well together.

Ernesto has $$$N$$$ ingredients in his trailer and he numbers them from $$$1$$$ to $$$N$$$. The first ingredients from $$$1$$$ to $$$P$$$ are all types of bread. The ingredients numbered from $$$P+1$$$ to $$$P+S$$$ are all types of sausage. The possible remaining ingredients numbered from $$$P+S+1$$$ to $$$N$$$ are various other ingredients. Ernesto will inform you of a list of $$$M$$$ pairs of ingredients that he thinks do not go well together and has asked for your help in determining how many different ways he can make hot dogs while respecting his rules.

Input

The first line of input contains $$$4$$$ integers, $$$N$$$, $$$M$$$, $$$P$$$, and $$$S$$$ $$$(2 \le N \le 20, 0 \le M \le \frac{N(N-1)}{2}, P \ge 1, S \ge 1, P+S \le N)$$$ which are the integers indicated in the statement.

The next $$$M$$$ lines contain two integers $$$A$$$ and $$$B$$$ $$$(A \ne B, 1 \le A,B \le N)$$$ indicating that ingredients $$$A$$$ and $$$B$$$ do not go well together (all pairs are different).

Output

Print only one line with an integer indicating the number of possible hot dogs.

Examples
Input
4 1 1 1
3 4
Output
3
Input
6 2 2 1
4 1
5 6
Output
9