C - Spread of Rumors Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

ある学校には N 人の生徒がおり、生徒には 1 から N までの番号が付けられています。

この学校では噂が独特な仕方で広まります。生徒間には M 個の有向の伝達関係があり、i 番目の伝達関係は順序対 (u_i, v_i) で表されます。これは「生徒 u_i があるステップで噂を受け取ると、次のステップで生徒 v_i に噂が伝わる」という一方向の関係を意味します。

噂の伝播はステップ 0, 1, 2, \ldots と同期的に進行します。各ステップ t で噂を受け取る生徒の集合を A_t とします。A_t は以下のように定まります。

  • ステップ 0： 最初に、生徒 S が外部から噂を聞きます。A_0 = \{S\} です。
  • ステップ t \geq 1： 直前のステップ t-1 で噂を受け取った生徒（すなわち A_{t-1} の要素）だけが噂を伝えます。具体的には、伝達関係 (u, v) であって u \in A_{t-1} を満たすものすべてについて、生徒 v がステップ t で噂を受け取ります。すなわち、

A_t = \{v \mid \text{ある } u \in A_{t-1} \text{ が存在して伝達関係 } (u, v) \text{ がある}\}

です。

ここで重要な点を補足します。

  • 生徒が噂を伝えられるのは、その生徒自身が噂を受け取った直後の 1 ステップだけです。 A_{t-1} に含まれていない生徒は、たとえ過去のステップで噂を受け取ったことがあっても、ステップ t では誰にも噂を伝えません。
  • A_t は集合であるため、ある生徒がステップ t で複数の生徒から同時に噂を受け取っても、A_t に含まれるのは 1 回と数えます。
  • ある生徒が過去のステップで既に噂を聞いたことがあっても、再び別のステップで A_t に含まれることがあり得ます。特にグラフにサイクルがある場合には、同じ生徒が複数の異なるステップで噂を受け取ることがあります。
  • A_{t-1} のどの要素からも伝達関係で到達できる生徒がいない場合、A_t = \emptyset（空集合）となり、以降のすべてのステップでも A_t = \emptyset です。

各生徒 i について、生徒 i が噂を受け取るステップの集合を T_i = \{t \geq 0 \mid i \in A_t\} とします。例えば、生徒 i がステップ 0, 2, 5 で噂を受け取ったなら T_i = \{0, 2, 5\} です。（サイクルの存在により T_i が無限集合になることもあり得ますが、以下のクエリでは K_j \leq N の範囲のみを問うため、有限の範囲だけを考えれば十分です。）

最初に噂を聞く生徒 S は 1 から N のいずれかの生徒を自由に選ぶことができます。

Q 個のクエリが与えられます。j 番目のクエリでは非負整数 K_j（0 \leq K_j \leq N）が与えられるので、以下の値を求めてください：

最初に噂を聞く生徒 S の選び方のうち、ステップ 0 からステップ K_j までの間（両端含む）にすべての生徒（1 から N まで）が少なくとも 1 回は噂を受け取るような S の個数。

すなわち、すべての生徒 i (1 \leq i \leq N) について T_i \cap \{0, 1, \ldots, K_j\} \neq \emptyset を満たすような S (1 \leq S \leq N) の個数を求めてください。

制約

  • 1 \leq N \leq 2000
  • 0 \leq M \leq \min(N(N-1), 50000)
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq u_i, v_i \leq N
  • u_i \neq v_i（自己ループはない）
  • 伝達関係に重複はない。すなわち、i \neq j ならば (u_i, v_i) \neq (u_j, v_j)
  • 0 \leq K_j \leq N
  • 入力はすべて整数である

入力

N M Q
u_1 v_1
u_2 v_2
\vdots
u_M v_M
K_1
K_2
\vdots
K_Q
  • 1 行目には、生徒の人数 N、伝達関係の個数 M、クエリの個数 Q が、スペース区切りで与えられる。
  • 続く M 行のうち i 行目 (1 \leq i \leq M) には、i 番目の伝達関係を表す u_i と v_i がスペース区切りで与えられる。これは、生徒 u_i がステップ t で噂を受け取ったとき（u_i \in A_t）、ステップ t+1 で生徒 v_i が噂を受け取る（v_i \in A_{t+1}）という有向の関係を表す。
  • 続く Q 行のうち j 行目 (1 \leq j \leq Q) には、j 番目のクエリにおけるステップ数の上限 K_j が与えられる。

出力

Q 行出力せよ。j 行目には、j 番目のクエリに対する答え、すなわちステップ 0 からステップ K_j までの間にすべての生徒が少なくとも 1 回は噂を受け取るような、最初に噂を聞く生徒 S の個数を出力せよ。

入力例 1

4 4 5
1 2
2 3
3 4
4 1
0
1
2
3
4

出力例 1

0
0
0
4
4

入力例 2

3 2 4
1 2
2 1
0
1
2
3

出力例 2

0
0
0
0

入力例 3

8 14 8
1 2
1 3
2 4
3 4
4 5
5 6
6 4
5 7
7 8
8 5
2 6
3 7
6 8
8 1
0
1
2
3
4
5
6
8

出力例 3

0
0
0
3
7
8
8
8

入力例 4

16 40 12
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 1
1 5
1 9
2 6
2 10
3 7
3 11
4 8
4 12
5 9
5 13
6 10
6 14
7 11
7 15
8 12
8 16
9 13
9 1
10 14
10 2
11 15
11 3
12 16
12 4
0
1
2
3
4
5
6
8
10
12
15
16

出力例 4

0
0
0
0
0
13
14
16
16
16
16
16

入力例 5

1 0 4
0
1
0
1

出力例 5

1
1
1
1

Score : 366 pts

Problem Statement

A school has N students, numbered from 1 to N.

Rumors spread in a unique way at this school. There are M directed transmission relationships between students, and the i-th transmission relationship is represented by the ordered pair (u_i, v_i). This means a one-way relationship: "if student u_i receives a rumor at a certain step, the rumor is transmitted to student v_i at the next step."

The propagation of the rumor proceeds synchronously through steps 0, 1, 2, \ldots. Let A_t denote the set of students who receive the rumor at each step t. A_t is determined as follows:

  • Step 0: Initially, student S hears the rumor from an external source. A_0 = \{S\}.
  • Step t \geq 1: Only the students who received the rumor at the immediately preceding step t-1 (i.e., the elements of A_{t-1}) transmit the rumor. Specifically, for all transmission relationships (u, v) satisfying u \in A_{t-1}, student v receives the rumor at step t. That is,

A_t = \{v \mid \text{there exists } u \in A_{t-1} \text{ such that there is a transmission relationship } (u, v)\}

Here are some important supplementary notes:

  • A student can only transmit the rumor during the single step immediately after they themselves received it. A student not in A_{t-1} does not transmit the rumor to anyone at step t, even if they received the rumor at some past step.
  • Since A_t is a set, even if a student receives the rumor from multiple students simultaneously at step t, they are counted only once in A_t.
  • Even if a student has already heard the rumor at a past step, they may be included in A_t again at a different step. In particular, when the graph contains cycles, the same student may receive the rumor at multiple different steps.
  • If no student is reachable via transmission relationships from any element of A_{t-1}, then A_t = \emptyset (the empty set), and A_t = \emptyset for all subsequent steps as well.

For each student i, let T_i = \{t \geq 0 \mid i \in A_t\} be the set of steps at which student i receives the rumor. For example, if student i receives the rumor at steps 0, 2, 5, then T_i = \{0, 2, 5\}. (Due to the existence of cycles, T_i may be an infinite set, but since the queries below only ask about the range K_j \leq N, it suffices to consider only a finite range.)

The student S who first hears the rumor can be freely chosen from any of the students 1 to N.

Q queries are given. For the j-th query, a non-negative integer K_j (0 \leq K_j \leq N) is given. Determine the following value:

Among all choices of the student S who first hears the rumor, the number of choices of S such that all students (from 1 to N) receive the rumor at least once during the period from step 0 to step K_j (inclusive of both endpoints).

In other words, find the number of S (1 \leq S \leq N) such that for all students i (1 \leq i \leq N), T_i \cap \{0, 1, \ldots, K_j\} \neq \emptyset holds.

Constraints

  • 1 \leq N \leq 2000
  • 0 \leq M \leq \min(N(N-1), 50000)
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq u_i, v_i \leq N
  • u_i \neq v_i (no self-loops)
  • There are no duplicate transmission relationships. That is, if i \neq j then (u_i, v_i) \neq (u_j, v_j)
  • 0 \leq K_j \leq N
  • All input values are integers

Input

N M Q
u_1 v_1
u_2 v_2
\vdots
u_M v_M
K_1
K_2
\vdots
K_Q
  • The first line contains the number of students N, the number of transmission relationships M, and the number of queries Q, separated by spaces.
  • The i-th of the following M lines (1 \leq i \leq M) contains u_i and v_i representing the i-th transmission relationship, separated by a space. This represents the directed relationship that when student u_i receives the rumor at step t (u_i \in A_t), student v_i receives the rumor at step t+1 (v_i \in A_{t+1}).
  • The j-th of the following Q lines (1 \leq j \leq Q) contains the upper limit on the number of steps K_j for the j-th query.

Output

Output Q lines. On the j-th line, output the answer to the j-th query, i.e., the number of students S who can be chosen as the first to hear the rumor such that all students receive the rumor at least once during the period from step 0 to step K_j.

Sample Input 1

4 4 5
1 2
2 3
3 4
4 1
0
1
2
3
4

Sample Output 1

0
0
0
4
4

Sample Input 2

3 2 4
1 2
2 1
0
1
2
3

Sample Output 2

0
0
0
0

Sample Input 3

8 14 8
1 2
1 3
2 4
3 4
4 5
5 6
6 4
5 7
7 8
8 5
2 6
3 7
6 8
8 1
0
1
2
3
4
5
6
8

Sample Output 3

0
0
0
3
7
8
8
8

Sample Input 4

16 40 12
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 1
1 5
1 9
2 6
2 10
3 7
3 11
4 8
4 12
5 9
5 13
6 10
6 14
7 11
7 15
8 12
8 16
9 13
9 1
10 14
10 2
11 15
11 3
12 16
12 4
0
1
2
3
4
5
6
8
10
12
15
16

Sample Output 4

0
0
0
0
0
13
14
16
16
16
16
16

Sample Input 5

1 0 4
0
1
0
1

Sample Output 5

1
1
1
1