← 返回题目列表

AtCoder · agc074_a

A. 传达拓扑顺序

中文机器翻译题面 查看原题

分数: 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.