# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Divine Tree

One day Thor gave **Nabil Bin Masterchief** a rooted tree consisting of **n** vertices. Unfortunately, During the fight with Hela, his tree was shattered and he doesn’t remember all it’s edges. He only managed to restore **m** edges of the initial tree.

Now as a good friend of Nabil, you have to count the number of distinct trees of size **n** with vertex 1 as root which contain all of the **m** edges.

## Input

The first line of the input contains two integers **n** and **m** (**1 ≤ n ≤ 13**,** 0 ≤ m < n**) — the number of vertices and the number of edges remembered by Nabil respectively.

Each of the next **m** lines contains two integers **U _{i}** and

**V**(

_{i}**1 ≤**

**U**,

_{i}**V**

_{i}**≤**

**n**,

**U**

_{i}**≠**

**V**) — the numbers of vertices connected by the i-th edge. It’s guaranteed that this set of edges is a subset of edges of some tree. Same edge will not be given more than once in input.

_{i}## Output

Print a single integer — the number of trees of size **n** that contain all of the **m** edges.

## Samples

Input | Output |
---|---|

5 2 4 1 4 2 | 15 |

Input | Output |
---|---|

3 1 2 1 | 2 |

Two rooted trees are considered to be distinct if there exists an edge that occur in one of them and doesn’t occur in the other one.

#### Nobel_ruettt

→

Login to submit