Cities And Explosions :
Difficulty Level : Medium
Submissions : 405
Asked In :
Marks :15
: 18 | : 0
There are $$$n$$$ cities $$$(1, 2,......., n)$$$ and $$$m$$$ roads and the cities are connected to other cities by those roads. Terrorists have planted bombs in every city. Each bomb will explode one after the other. First bomb in city $$$1$$$ will explode, then city $$$2$$$ and so on.
Each explosion will destroy the city and the roads which are connected to it.
After every explosion, you need to return the number of connected components of cities.
The first line of each testcase contains two space separated integers $$$n$$$ $$$(1 \le n \le 10^5)$$$ and $$$m$$$ $$$(1 \le m \le min(n,2 \cdot 10^5)$$$ — the number of cities and the number of roads.
The next $$$m$$$ lines contain two space separated integers $$$u$$$ and $$$v$$$ $$$(1 \le u,v \le n)$$$ each denoting that there is a road between city number $$$u$$$ and city number $$$v$$$.
Print $$$n$$$ integers each in a new line — $$$i^{th}$$$ integer should be the number of connected components after the $$$i^{th}$$$ node explodes.
6 7 1 2 1 4 1 5 2 4 2 3 3 5 3 6
1 2 3 2 1 0
For the sample test case, the following images show the number of components after successive explosion of the cities.
 |  |  |  |  |  |  |
