問題一覧 > 通常問題

No.2585 How many "Who is Santa?"

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 1.225秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 42
作問者 : netyo715 / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 10345 / 自分の提出
問題文最終更新日: 2023-11-16 11:51:22
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

You are given an integer $N$.
You have decided to create test cases for the following problem "Who is Santa?" in which the input value $M$ equals $N$.
Among the inputs satisfying the constraints of "Who is Santa?", print the number of those with $M=N$, modulo $998244353$.
See the samples for details.


Who is Santa?

Problem Statement

There are $M$ people numbered from $1$ to $M$.
Exactly $1$ of the $M$ people is Santa, and all $M$ people know who it is.
Person $i$ makes a statement about person $A_i(i \neq A_i)$: that they are not Santa when $L_i = 0$, and that they are Santa when $L_i = 1$.
Santa always lies, and everyone who is not Santa always tells the truth.
The people make their statements so that Santa is uniquely determined as $1$ person.

What it means for Santa to be uniquely determined as $1$ person

Santa is said to be uniquely determined as $1$ person from the statements when there exists exactly $1$ integer $i$ satisfying all of the following conditions.

  • Person $i$ says that person $A_i$ is Santa.
  • Person $i$ is the only one who says that someone other than person $i$ is Santa.
  • No one says that person $i$ is not Santa.

Find the number of the person who is Santa.

Input

$M$
$L_1$ $A_1$
$L_2$ $A_2$
:
$L_M$ $A_M$

  • All inputs are integers
  • $2 \leq M$
  • $L_i \in \{0, 1\}$
  • $1 \leq A_i \leq M$
  • $A_i \neq i$
  • Santa is uniquely determined as $1$ person from the input

Output

Print the number of the person who is Santa.

Sample

Input
3
1 2
1 1
0 1
Output
2

  • Person $1$ says that person $2$ is Santa.
  • Person $2$ says that person $1$ is Santa.
  • Person $3$ says that person $1$ is not Santa.


Input

$N$

  • $N$ is an integer
  • $2 \leq N \leq 20231225$

Output

Among the inputs satisfying the constraints of "Who is Santa?", print the number of those with $M=N$, modulo $998244353$.
Print a newline at the end.

Sample

Sample 1
Input
3
Output
24

Among the inputs of "Who is Santa?", $24$ satisfy the constraints.
For example, the following input satisfies all the constraints and is one of the $24$ inputs.

3
1 2
1 1
0 2

The following input does not satisfy the constraint "Santa is uniquely determined as $1$ person from the input" and is not one of the $24$ inputs.

3
1 2
1 3
1 1
Sample 2
Input
4
Output
312

For example, the following input does not satisfy the constraint "Santa is uniquely determined as $1$ person from the input" and is not one of the $312$ inputs.

4
1 2
1 1
0 4
0 3
Sample 3
Input
3018570
Output
1213

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。