P6121 [USACO16OPEN] Closing the Farm G

*This problem has the same meaning as the [Silver problem with the same name](/problem/P3144). The only difference is the Constraints.*

FJ and his cows are planning to leave the town for a long trip, and FJ wants to temporarily shut down his farm to save some money. There are $N$ barns on the farm, connected by $M$ bidirectional roads ($1 \leq N,M \leq 2 \times 10^5$). To shut down the entire farm, FJ plans to close exactly one barn at a time. When a barn is closed, all roads connected to that barn are also closed and can never be used again. FJ is interested in knowing whether his farm is "fully connected" at each moment (here, "moment" means the time before each barn is closed) — that is, starting from any open barn, it is possible to reach any other open barn. Note that after some moment, the entire farm may no longer be "fully connected".

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, indicating the index of the barn closed at the $i$-th step.

Output $N$ lines. Each line contains `YES` or `NO`, indicating whether the farm is fully connected at that moment. The first line is the initial state. Line $i$ ($2 \leq i \leq N$) is the state after the $(i-1)$-th barn has been closed.

Translated by ChatGPT 5