分数: 700 点
问题陈述
给你一个简单的有向无环图 G 与 N 顶点编号 1 to N. G 有 M 边缘,以及 i第一条边从顶点定向 x_i 到顶点 y_i.
排列 满足以下条件的 P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) 称为 特殊排列:
- P_{x_i} \lt P_{y_i} 对于所有人 i=1,2,\cdots,M.
你有一个特殊的排列 P。 高桥和青木将用它玩游戏。 高桥知道每一项的价值 P,但青木只知道 P 是一个特殊的排列。 两人都知道 G。 高桥选择了一些术语 P 并告诉青木他们的立场和价值观。 求高桥需要告诉青木的最少项数,以便青木可以确定所有项的值 P.
解决 T 每个输入的测试用例。
约束
- 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} \lt P_{y_i}
- 总和 N 所有测试用例最多 2 \times 10^5.
- 总和 M 所有测试用例最多 2 \times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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.