Combustion and Connectivity Components#4371
Once, you observed a fascinating process: a graph burning. Initially, the graph burns while staying connected. However, as time progresses, it begins to break into separate connected components, and eventually, these components completely burn out and vanish.
You found this process so intriguing that you decided to simulate it on your computer. To do this, you need to answer the following question: How many connected components of unburned vertices will remain in the graph after seconds of burning? You need to determine the answer for each from to , where is the time when the last vertex burns.
The first line contains the integers , , and (1 \leq N, M \leq 10^5, 1 \leq S \leq N)—representing the number of vertices, the number of edges, and the ignition vertex, respectively. The next lines describe the edges of the graph with two integers and (1 \leq a, b \leq N)—the endpoints of each edge. The graph may include multiple edges and loops.
On the first line, output the number —the time when the last vertex burns. Assume that vertex ignites at time t = 1 second, and the fire spreads to any adjacent vertex in one second. On the next line, output K + 1 numbers separated by spaces, where the -th number represents the number of connected components consisting of vertices that have not yet burned at the end of seconds (0 \leq i \leq K).
Explanation: In the first example, at seconds, before ignition, the graph is connected, so there is connected component. At the end of the st second, vertex burns, splitting the graph into two components: and (1, 3, 4). After the nd second, vertices , , and burn, leaving only vertex as a connected component. After the rd second, vertex burns, and no connected components remain, as all vertices have burned.
In the second example, at seconds, the graph consists of three separate vertices, forming connected components. When the first vertex ignites, it burns in the st second, leaving two connected components. Since no other vertices will burn, the burning time is second.
Example
5 5 2
1 2
1 3
1 4
3 4
3 53
1 2 1 0Example
3 0 11
3 2Example 1