A - Communicate Topological Order Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 700 点

問題文

頂点に 1 から N までの番号がついた N 頂点の単純有向非巡回グラフ G が与えられます。 G には M 本の辺があり、i 番目の辺は頂点 x_i から頂点 y_i へ張られています。

(1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_N) であって以下の条件を満たすものを特別な順列と呼ぶことにします。

  • すべての i=1,2,\cdots,M について、P_{x_i} \lt P_{y_i}

特別な順列 P が与えられます。 これを使って高橋君と青木君がゲームをします。 高橋君 は P の各項の値を知っていますが、青木君は P が特別な順列であるということしか知りません。 なお、二人とも G の形は知っています。 高橋君は P のいくつかの項を選び、その位置と値を青木君に伝えます。 青木君が P のすべての項の値を特定するために高橋君が伝える必要がある項の個数の最小値を求めてください。

1 つの入力につき、T 個のテストケースを解いてください。

制約

  • 1 \leq T \leq 10^4
  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq x_i,y_i \leq N
  • 与えられるグラフ G は単純有向非巡回グラフ
  • 1 \leq P_i \leq N
  • P_1,P_2,\ldots,P_N は互いに相異なる
  • P_{x_i} \lt P_{y_i}
  • 全てのテストケースにおける N の総和は 2 \times 10^5 以下
  • 全てのテストケースにおける M の総和は 2 \times 10^5 以下
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

T
case_1
case_2
\vdots
case_T

各ケースは以下の形式で与えられる。

N M  
x_1 y_1  
x_2 y_2  
\vdots  
x_M y_M  
P_1 P_2 \ldots P_N

出力

答えを合計 T 行で出力せよ。 t 行目には、t 番目のテストケースの答えを出力せよ。

入力例 1

3
5 4
3 4
4 1
3 1
5 2
5 4 1 2 3
4 0
4 2 1 3
10 15
6 2
8 5
4 9
7 10
3 7
5 6
8 9
3 5
5 2
8 2
3 9
5 9
10 2
3 2
7 4
8 9 2 6 4 5 3 1 10 7

出力例 1

2
3
6

1 つ目のケースでは、高橋君が P_1=5, \; P_4=2 であることを伝えると、青木君は P のすべての項を特定することができます。また、高橋君が P のいずれの項を 1 つだけ伝えたとしても、青木君は P のすべての項を特定することはできません。

Score : 700 points

Problem Statement

You are given a simple directed acyclic graph G with N vertices numbered 1 to N. G has M edges, and the i-th edge is directed from vertex x_i to vertex y_i.

A permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) that satisfies the following condition is called a special permutation:

  • P_{x_i} \lt P_{y_i} for all i=1,2,\cdots,M.

You are given a special permutation P. Takahashi and Aoki will play a game using it. Takahashi knows the value of each term of P, but Aoki only knows that P is a special permutation. Both of them know G. Takahashi selects some terms of P and tells Aoki their positions and values. Find the minimum number of terms that Takahashi needs to tell Aoki so that Aoki can determine the values of all terms of P.

Solve T test cases per input.

Constraints

  • 1 \leq T \leq 10^4
  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq x_i,y_i \leq N
  • The given graph G is a simple directed acyclic graph.
  • 1 \leq P_i \leq N
  • P_1,P_2,\ldots,P_N are pairwise distinct.
  • P_{x_i} \lt P_{y_i}
  • The sum of N over all test cases is at most 2 \times 10^5.
  • The sum of M over all test cases is at most 2 \times 10^5.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each case is given in the following format:

N M  
x_1 y_1  
x_2 y_2  
\vdots  
x_M y_M  
P_1 P_2 \ldots P_N

Output

Output T lines in total. The t-th line should contain the answer for the t-th test case.

Sample Input 1

3
5 4
3 4
4 1
3 1
5 2
5 4 1 2 3
4 0
4 2 1 3
10 15
6 2
8 5
4 9
7 10
3 7
5 6
8 9
3 5
5 2
8 2
3 9
5 9
10 2
3 2
7 4
8 9 2 6 4 5 3 1 10 7

Sample Output 1

2
3
6

In the first case, if Takahashi tells that P_1=5, \; P_4=2, Aoki can determine all terms of P. Also, if Takahashi tells only one term of P, Aoki cannot determine all terms of P.