[USACO16OPEN] Closing the Farm S

 1 Sec 128 MB |  Markdown 获取标签
182135
通过人数尝试人数总提交数

 

题目描述

FJ 和他的奶牛们正在计划离开小镇做一次长的旅行,同时 FJ 想临时地关掉他的农场以节省一些金钱。

这个农场一共有被用 MM 条双向道路连接的 NN 个谷仓(1N,M30001 \leq N,M \leq 3000)。为了关闭整个农场,FJ 计划每一次关闭掉一个谷仓。当一个谷仓被关闭了,所有的连接到这个谷仓的道路都会被关闭,而且再也不能够被使用。

FJ 现在正感兴趣于知道在每一个时间(这里的“时间”指在每一次关闭谷仓之前的时间)时他的农场是否是“全连通的”——也就是说从任意的一个开着的谷仓开始,能够到达另外的一个谷仓。注意自从某一个时间之后,可能整个农场都开始不会是“全连通的”。

输入格式

输入第一行两个整数 N,MN,M

接下来 MM 行,每行两个整数 u,vu,v1u,vN1 \leq u,v \leq N),描述一条连接 u,vu,v 两个农场的路。

最后 NN 行每行一个整数,表示第 ii 个被关闭的农场编号。

输出格式

输出 NN 行,每行包含 YESNO,表示某个时刻农场是否是全连通的。

第一行输出最初的状态,第 ii 行(2iN2 \leq i \leq N)输出第 i1i-1 个农场被关闭后的状态。

样例输入 #1

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

样例输出 #1

YES
NO
YES
YES

来源

洛谷P3144

 

 您尚未登录,无法进行代码提交

2025寒假新生集训二(并查集&倍增&ST表&最近公共祖先)

2025-01-12 09:30
2025-01-12 21:30
Ended