No.2588 Increasing Record
問題文最終更新日: 2023-12-12 23:49:08
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
Advent Calendar Contest 2023
(順位表)
の他の問題:
Problem Statement
There is a simple connected undirected graph with $N$ vertices and $M$ edges. The $i$-th edge connects vertices $u_i$ and $v_i$.
Takahashi creates a sequence $X$ by the following procedure.
- First, he chooses any vertex $k(1 \le k \le N)$, moves to that vertex, and initializes the sequence $X$ as a sequence consisting of a single $k$ ($1$ element).
- He repeats the following action $0$ or more times.
- He chooses a vertex $v$ adjacent to the vertex he is currently at and moves to that vertex. Then, if $v$ is greater than the last element of $X$, he appends $v$ to the end of $X$.
Find the number of possible final sequences $X$, modulo $998244353$.
Input
$N\ M$ $u_1\ v_1$ $u_2\ v_2$ $\vdots$ $u_M\ v_M$
- All input values are integers.
- $2 \le N \le 2 \times 10^5$
- $1 \le M \le 2 \times 10^5$
- $1 \le u_i < v_i \le N$
- The given graph is simple and connected.
Output
Find the number of possible final sequences $X$, modulo $998244353$. Print a newline at the end.
Sample
Sample 1
Input
4 3 1 2 1 4 3 4
Output
9
For example, the following sequence of actions is possible.
- Takahashi chooses vertex $1$. Now $X = (1)$.
- Takahashi moves to vertex $2$. Now $X = (1,2)$.
- Takahashi moves to vertex $1$. $X = (1,2)$ remains unchanged.
- Takahashi moves to vertex $4$. Now $X = (1,2,4)$.
- Takahashi moves to vertex $3$. $X = (1,2,4)$ remains unchanged.
Sample 2
Input
4 4 1 2 2 3 3 4 1 4
Output
13
Sample 3
Input
8 9 1 5 6 8 4 5 7 8 1 8 5 6 1 3 3 8 2 4
Output
38
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
tute7627
SPD_9X2