We will perform the following operation on a complete undirected graph $G$ with $N$ vertices.

> For each $i = 1, 2, \ldots, M$, delete the undirected edge connecting vertices $u_i$ and $v_i$.

Determine if there is a path from vertex $1$ to vertex $N$ in $G$ after the operation. If there is, find the number, modulo $998244353$, of shortest paths from vertex $1$ to vertex $N$.

Here, a shortest path from vertex $1$ to vertex $N$ is a path from vertex $1$ to vertex $N$ that contains the minimum number of edges.

The input is given from Standard Input in the following format:

```
$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$
```

If there is no path from vertex $1$ to vertex $N$ in $G$ after the operation, print `-1`. If there is, print the number, modulo $998244353$, of shortest paths from vertex $1$ to vertex $N$.

-   $2 \leq N \leq 2 \times 10^5$
-   $0 \leq M \leq \min\lbrace 2 \times 10^5, N(N-1)/2 \rbrace$
-   $1 \leq u_i, v_i \leq N$
-   $u_i \neq v_i$
-   $i \neq j \implies \lbrace u_i, v_i \rbrace \neq \lbrace u_j, v_j \rbrace$
-   All input values are integers.