Closing the Farm

题目描述

农夫约翰和他的奶牛们计划离开城镇去度一个长假，因此 FJ 想要暂时关闭他的农场以节省开支。 农场由 $N$ 个牛棚组成，并且在某些牛棚对之间有 $M$ 条双向路径连接（$1 \leq N, M \leq 3000$）。为了关闭农场，FJ 计划一次关闭一个牛棚。当一个牛棚关闭时，与该牛棚相邻的所有路径也会关闭，并且之后不能再使用。 FJ 想在每个时间点（初始时，以及每次关闭之后）知道他的农场是否“完全连通”——也就是说，是否可以沿着一系列合适的路径，从任何一个仍然开放的牛棚到达任何另一个仍然开放的牛棚。由于 FJ 的农场一开始就有些破败，它甚至可能在初始时就不是完全连通的。

输入格式

第一行输入包含 $N$ 和 $M$。接下来的 $M$ 行每行用一对牛棚编号描述一条路径所连接的两个牛棚（牛棚编号为 $1 \ldots N$）。最后的 $N$ 行给出一个 $1 \ldots N$ 的排列，描述牛棚将被关闭的顺序。

输出格式

输出包含 $N$ 行，每行是 "YES" 或 "NO"。 第一行表示初始农场是否完全连通；第 $i+1$ 行表示在第 $i$ 次关闭之后农场是否完全连通。

4 3
1 2
2 3
3 4
3
4
1
2

YES
NO
YES
YES

提示

题目来源：Yang Liu

标签: USACO|2016|Silver

来源

USACO|2016|Silver