AT_agc074_a [AGC074A] Communicate Topological Order

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.

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 $ T $ lines in total. The $ t $ -th line should contain the answer for the $ t $ -th test case.

### Sample Explanation 1 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 $ . ### 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.