P3144 [USACO16OPEN] Closing the Farm S

This problem has the same statement as the problem with the same name in the Gold division, with the only difference being the constraints. See [the problem with the same name in the Gold division](/problem/P6121).

FJ and his cows are planning to leave town for a long trip, and FJ wants to temporarily shut down his farm to save some money. The farm has $N$ barns connected by $M$ bidirectional roads ($1 \leq N,M \leq 3000$). To close the entire farm, FJ plans to close one barn at a time. When a barn is closed, all roads incident to that barn are closed and can no longer be used. FJ is interested in knowing, at each time (here, “time” means the moment just before each barn is closed), whether his farm is “fully connected” — that is, from any open barn, it is possible to reach any other open barn. Note that from some time onward, the entire farm may cease to be fully connected. # Description

The first line contains two integers $N,M$. The next $M$ lines each contain two integers $u,v$ ($1 \leq u,v \leq N$), describing a road connecting barns $u$ and $v$. The last $N$ lines each contain one integer, where the $i$-th line gives the index of the $i$-th barn to be closed.

Output $N$ lines, each containing `YES` or `NO`, indicating whether the farm is fully connected at that time. Print the initial status on the first line. On line $i$ ($2 \leq i \leq N$), print the status after the $(i-1)$-th barn has been closed.

Translated by ChatGPT 5