Bajtazar 在一年多前成为了 Bajtocja 的旅行爱好者。这个国家有 $n$ 个城市，由 $m$ 条双向道路连接。Bajtazar 特别喜欢“非凡旅行”。在这些旅行中，他从某个城市出发，沿着 Bajtocja 的道路移动，访问不同的城市，最后回到出发城市。在旅行过程中，他既不能访问任何城市两次（出发城市除外），也不能使用任何连接两次。

Bajtocja 的所有道路最初都是黑色的。Bajtazar 对此感到不满，因此在下一次非凡旅行中，他会将所经过的每一条道路涂成金丝雀黄色。他有多少种不同的方式来给道路涂色？如果两种涂色方案中存在某条道路的颜色不同，则认为这两种涂色方案是不同的。

输入格式

第一行包含两个整数 $n, m$ ($2 \le n \le 20, 1 \le m \le \frac{n(n-1)}{2}$)。接下来的 $m$ 行，每行包含两个自然数 $u_i, v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，表示城市 $u_i$ 和 $v_i$ 之间有一条双向道路。任意两个城市之间最多只有一条道路连接。

输出格式

输出一行，包含一个整数，表示可能达到的不同道路涂色方案的数量。

样例

输入 1

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

输出 1

3