問題一覧 > 通常問題

No.2588 Increasing Record

レベル : / AI推定難易度 : 2625 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 24
作問者 : 👑 tute7627 / テスター : SPD_9X2 👑 rin204
お気に入りにしたユーザー ProblemId : 10389 / 自分の提出
問題文最終更新日: 2023-12-12 23:49:08
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.

  1. 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).
  2. 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.

  1. Takahashi chooses vertex $1$. Now $X = (1)$.
  2. Takahashi moves to vertex $2$. Now $X = (1,2)$.
  3. Takahashi moves to vertex $1$. $X = (1,2)$ remains unchanged.
  4. Takahashi moves to vertex $4$. Now $X = (1,2,4)$.
  5. 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もしくは右上の雲マークをクリックしてアカウントを作成してください。