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.