Closing the Farm

题目描述

农夫约翰和他的奶牛们正计划离开城镇去度一个长假，因此 FJ 想在这段时间里暂时关闭他的农场以节省开支。 农场由 $N$ 个谷仓组成，并且在某些谷仓对之间有 $M$ 条双向路径连接（$1 \leq N, M \leq 200,000$）。为了关闭农场，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|Gold

来源

USACO|2016|Gold