题目描述

给定一张有 $n$ 个结点、$m$ 条边的无向图，保证每个结点的度数不超过 $10$。

从结点 $1$ 出发，每走到一个当前路径中从未出现过的结点，就得到一条不同的简单路径；长度为零、只包含结点 $1$ 的路径也计入。请输出简单路径总数与 $10^6$ 的较小值。简单路径中不能出现重复结点。

输入格式

第一行输入两个正整数 $n,m$。接下来 $m$ 行，每行输入两个整数 $u_i,v_i$，表示一条无向边。

输出格式

输出一个整数，表示 $\min(k,10^6)$，其中 $k$ 为从结点 $1$ 出发的简单路径总数。

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

6

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

27

2 1
1 2

2

数据范围与约定

$1\le n,m\le2\times10^5$，每个结点的度数不超过 $10$。