AT_agc074_a.[AGC074A] Communicate Topological Order

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

给定一个简单的有向无环图 $G$ ，有 $N$ 个顶点，编号为 $1$ 到 $N$ 。 $G$ 有 $M$ 条边，第 $i$ 条边从顶点 $x_i$ 指向顶点 $y_i$ 。

一个排列 $P=(P_1,P_2,\ldots,P_N)$ ，如果满足以下条件，则称为特殊排列：

现在给定一个特殊排列 $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

3
5 4
3 4
4 1
3 1
5 2
5 4 1 2 3
4 0
4 2 1 3
10 15
6 2
8 5
4 9
7 10
3 7
5 6
8 9
3 5
5 2
8 2
3 9
5 9
10 2
3 2
7 4
8 9 2 6 4 5 3 1 10 7

输出#1

2
3
6

在第一组样例中，如果高桥告诉青木 $P_1=5, \; P_4=2$ ，那么青木就能确定全部的 $P$ 。并且，如果只告诉一项 $P$ 的信息，青木无法确定全部的 $P$ 。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?