AT_agc074_a [AGC074A] Communicate Topological Order

頂点に $ 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 $ 個のテストケースを解いてください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ 番目のテストケースの答えを出力せよ。

### Sample Explanation 1 $ 1 $ つ目のケースでは、高橋君が $ P_1=5, \; P_4=2 $ であることを伝えると、青木君は $ P $ のすべての項を特定することができます。また、高橋君が $ P $ のいずれの項を $ 1 $ つだけ伝えたとしても、青木君は $ P $ のすべての項を特定することはできません。 ### 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 $ - 与えられるグラフ $ 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 $ 以下 - 入力される値は全て整数