题目描述

给定一张 $n$ 个节点 $m$ 条边的无向图，保证每个节点的度数 $\le10$ 。

记从任意节点回到 $1$ 号点的不同简单路径总数为 $K$ ，请输出 $min(K,10^6)$ 。

定义：简单路径是不经过重复结点的路径。

输入格式

第一行输入两个整数 $n,m$ 。

接下来 $m$ 行，每行输入两个整数 $u_i,v_i$ 。

输出格式

输出题目要求的答案。

输入输出样例 #1

输入 #1

4 2
1 2
2 3

输出 #1

3

输入输出样例 #2

输入 #2

4 6
1 2
1 3
1 4
2 3
2 4
3 4

输出 #2

16

输入输出样例 #3

输入 #3

8 21
2 6
1 3
5 6
3 8
3 6
4 7
4 6
3 4
1 5
2 4
1 2
2 7
1 4
3 5
2 5
2 3
4 5
3 7
6 7
5 7
2 8

输出 #3

2023

说明/提示

• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $0\ \leq\ M\ \leq\ \min\ \left(2\ \times\ 10^5,\ \frac{N(N-1)}{2}\right)$
• $1\ \leq\ u_i,\ v_i\ \leq\ N$
• 给定的图是简单图
• 每个点的度 $\le 10$