{"problem":{"name":"Counting Shortest Paths","description":{"content":"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$. Determ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc319_g"},"statements":[{"statement_type":"Markdown","content":"We will perform the following operation on a complete undirected graph $G$ with $N$ vertices.\n\n> For each $i = 1, 2, \\ldots, M$, delete the undirected edge connecting vertices $u_i$ and $v_i$.\n\nDetermine 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$.\nHere, 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.\n\n## Constraints\n\n*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $0 \\leq M \\leq \\min\\lbrace 2 \\times 10^5, N(N-1)/2 \\rbrace$\n*   $1 \\leq u_i, v_i \\leq N$\n*   $u_i \\neq v_i$\n*   $i \\neq j \\implies \\lbrace u_i, v_i \\rbrace \\neq \\lbrace u_j, v_j \\rbrace$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$\\vdots$\n$u_M$ $v_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc319_g","tags":[],"sample_group":[["6 7\n4 3\n1 3\n2 4\n1 6\n4 6\n5 1\n6 2","3\n\nIn $G$ after the operation, the shortest paths from vertex $1$ to vertex $N$ are the following three, each containing three edges.\n\n*   vertex $1$ $\\rightarrow$ vertex $2$ $\\rightarrow$ vertex $3$ $\\rightarrow$ vertex $6$\n*   vertex $1$ $\\rightarrow$ vertex $2$ $\\rightarrow$ vertex $5$ $\\rightarrow$ vertex $6$\n*   vertex $1$ $\\rightarrow$ vertex $4$ $\\rightarrow$ vertex $5$ $\\rightarrow$ vertex $6$"],["4 6\n1 2\n1 3\n1 4\n2 3\n2 4\n3 4","\\-1\n\n$G$ has no edges after the operation. There is no path from vertex $1$ to vertex $N$, so print `-1`."]],"created_at":"2026-03-03 11:01:14"}}