Given an undirected connected graph $G$, it is known that $G$ becomes a cactus graph after removing one edge (a cactus graph is an undirected connected graph where no two simple cycles share a common edge). Find the number of spanning trees of $G$. The result should be taken modulo $998244353$.

Input

The first line contains two integers $n$ and $m$, representing the number of vertices and edges in graph $G$.

The next $m$ lines each contain two space-separated positive integers $u, v$ ($1\le u, v\le n$), representing an edge $(u,v)\in G$.

Output

Output a single integer representing the number of spanning trees of $G$ modulo $998244353$.

Examples

Input 1

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

Output 1

8

Subtasks

For all data, $1\le n\le m\le 5\times 10^5$.

• For $10\%$ of the data, $1\le n=m\le 2000$.
• For another $40\%$ of the data, $1\le n,m\le 10^5$ and $G$ itself is a cactus graph.
• For the remaining $50\%$ of the data, there are no special restrictions.