{"raw_statement":[{"iden":"problem statement","content":"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$.\nA permutation $P=(P_1,P_2,\\ldots,P_N)$ of $(1,2,\\ldots,N)$ that satisfies the following condition is called a **special permutation**:\n\n*   $P_{x_i} \\lt P_{y_i}$ for all $i=1,2,\\cdots,M$.\n\nYou 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$.\nSolve $T$ test cases per input."},{"iden":"constraints","content":"*   $1 \\leq T \\leq 10^4$\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $0 \\leq M \\leq 2 \\times 10^5$\n*   $1 \\leq x_i,y_i \\leq N$\n*   The given graph $G$ is a simple directed acyclic graph.\n*   $1 \\leq P_i \\leq N$\n*   $P_1,P_2,\\ldots,P_N$ are pairwise distinct.\n*   $P_{x_i} \\lt P_{y_i}$\n*   The sum of $N$ over all test cases is at most $2 \\times 10^5$.\n*   The sum of $M$ over all test cases is at most $2 \\times 10^5$.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$case_1$\n$case_2$\n$\\vdots$\n$case_T$\n\nEach case is given in the following format:\n\n$N$ $M$  \n$x_1$ $y_1$  \n$x_2$ $y_2$  \n$\\vdots$  \n$x_M$ $y_M$  \n$P_1$ $P_2$ $\\ldots$ $P_N$"},{"iden":"sample input 1","content":"3\n5 4\n3 4\n4 1\n3 1\n5 2\n5 4 1 2 3\n4 0\n4 2 1 3\n10 15\n6 2\n8 5\n4 9\n7 10\n3 7\n5 6\n8 9\n3 5\n5 2\n8 2\n3 9\n5 9\n10 2\n3 2\n7 4\n8 9 2 6 4 5 3 1 10 7"},{"iden":"sample output 1","content":"2\n3\n6\n\nIn 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$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}