题目描述

Zhenya 在物理实践课上学习电学。他要分析一个电路网络。

电路网络由若干节点和导线组成，其中一个节点是源点，另一个节点是汇点。本题中的电路网络都是“正确”的。

正确电路网络定义如下：

• 基础网络：源点和汇点之间由一根导线相连，是正确网络；
• 若 $A$ 和 $B$ 是正确网络，则 $S(A,B)$ 也是正确网络：将 $A$ 的汇点与 $B$ 的源点合并。新网络源点为 $A$ 的源点，汇点为 $B$ 的汇点；
• 若 $A$ 和 $B$ 是正确网络，则 $P(A,B)$ 也是正确网络：将两个网络的源点合并、汇点合并。新网络的源点和汇点就是合并后的两个点；
• 所有正确网络都可以由基础网络通过有限次上述串联和并联操作得到。

Zhenya 不喜欢物理，但喜欢图论。因此他想计算，有多少种删除若干导线的方法，使剩下的导线构成一棵树：即任意两个节点之间恰好有一条路径。

答案可能很大，请对 $998244353$ 取模。

输入格式

第一行两个整数 $n,m$，表示节点数和导线数。

接下来 $m$ 行，每行两个整数 $a,b$，表示节点 $a$ 与节点 $b$ 之间有一根导线。

约束：

• $1 \le n,m \le 100000$；
• $1 \le a,b \le n$，$a\ne b$；
• 保证给定网络是正确网络；
• 源点为 $1$，汇点为 $n$；
• 网络中允许重边。

输出格式

输出删除若干导线后剩余导线构成树的方案数，模 $998244353$。

样例 1 输入

3 3
1 2
2 3
3 1

样例 1 输出

3

样例 2 输入

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

样例 2 输出

15

样例 3 输入

2 2
1 2
1 2

样例 3 输出

2

说明

第一个和第三个样例中，删除任意一根导线均可。第二个样例中，可以删除导线 $(1,6)$ 和任意另一根导线，或者从两条链 $1-2-4-6$ 与 $1-3-5-6$ 中各删除一根导线。