You are given an (undirected) graph ~G~ with ~n~ vertices and ~m~ edges. You are also given a tree ~T~ with ~n~ vertices. The vertices of the tree and of the graph are numbered ~1,\ldots,n~.

You need to find the number of permutations ~p~ of ~1,\ldots,n~ such that if ~(i,j)~ is an edge of tree ~T~, ~(p_i,p_j)~ is an edge of graph ~G~. The converse doesn't have to be true: it is possible that if ~(p_i,p_j)~ is an edge of ~G~, ~(i,j)~ is not an edge of tree ~T~.

Input Specification

The first line of the input consists of two positive integers ~n,m~ denoting the number of nodes and the number of edges in ~G~.

In the following ~m~ lines, each line consists of two positive integers ~u,v~ denoting that there is an edge ~(u,v)~ in ~G~.

In the following ~n-1~ lines, each line consists of two positive integers ~u,v~ denoting that there is an edge ~(u,v)~ in ~T~.

Output Specification

Output the number of valid permutations ~p~ satisfying the above constraints. If there is no such permutation ~p~, output ~0~.

Sample Input 1

5 4
1 2
1 3
1 4
1 5
3 1
3 2
3 4
3 5

Sample Output 1

24

Explanation

We must map vertex ~3~ of the tree ~T~ to vertex ~1~ of the graph ~G~. Afterwards, we can simply map vertices ~1,2,4,5~ of ~T~ to vertices ~2,3,4,5~ of ~G~ in any order. So the answer is ~4! = 24~.

Sample Input 2

6 12
1 2
1 4
1 5
1 6
2 3
2 4
2 6
3 4
3 5
3 6
4 5
4 6
3 4
4 1
1 6
6 5
4 2

Sample Output 2

196

Constraints

For all test cases, ~1 \leq n \leq 19, 1 \leq m \leq \frac{n(n-1)}{2}~.

It is guaranteed that there are no parallel edges or self loops in graph ~G~.

• Subtask 1 (14 points): ~n \leq 10~.
• Subtask 2 (10 points): it is guaranteed that ~T~ is a path: equivalently, it is a tree whose maximum degree is at most 2. A path with ~n~ vertices ~v_1,\ldots,v_n~ has edges ~v_1v_2,\ldots,v_{n-1}v_n~.
• Subtask 3 (10 points): ~n \leq 14~. Depends on Subtask 1.
• Subtask 4 (15 points): ~n \leq 16~, and the answer is at most ~10^5~.
• Subtask 5 (16 points): ~n \leq 16~. Depends on Subtask 1,3,4.
• Subtask 6 (35 points): no additional constraints. Depends on all previous subtasks.