AT_agc074_a [AGC074A] Communicate Topological Order

给定一个简单的有向无环图 $G$，有 $N$ 个顶点，编号为 $1$ 到 $N$。$G$ 有 $M$ 条边，第 $i$ 条边从顶点 $x_i$ 指向顶点 $y_i$。 一个排列 $P=(P_1,P_2,\ldots,P_N)$，如果满足以下条件，则称为**特殊排列**： - 对于所有 $i=1,2,\cdots,M$，都有 $P_{x_i} < P_{y_i}$。 现在给定一个特殊排列 $P$。高桥和青木将用这个排列玩一个游戏。高桥知道排列 $P$ 的每一项的值，而青木只知道 $P$ 是特殊排列。且他们都知道图 $G$。高桥会选择 $P$ 中的一些项，并将这些项的位置和值告诉青木。请你计算，为了使青木能够确定 $P$ 的全部项，最少需要透露多少项的信息。 请解答 $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$ 组测试数据的答案。

### 样例解释 1 在第一组样例中，如果高桥告诉青木 $P_1=5, \; P_4=2$，那么青木就能确定全部的 $P$。并且，如果只告诉一项 $P$ 的信息，青木无法确定全部的 $P$。 ### 约束条件 - $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} < P_{y_i}$ - 所有测试数据中 $N$ 的总和不超过 $2 \times 10^5$ - 所有测试数据中 $M$ 的总和不超过 $2 \times 10^5$ - 输入数据均为整数。 由 ChatGPT 5 翻译