Сгорание и компоненты связности
Однажды Вы наблюдали, как сгорает граф – это очень интересный процесс. Сначала граф горит, но остаётся связным, потом в какой-то момент он начинает распадаться на отдельные связные куски, а через некоторое время эти отдельные куски совсем сгорают и исчезают.
Вам так понравилось смотреть на горение графа, что Вы решили промоделировать его на своём компьютере. Для этого Вам необходимо ответить на такой вопрос: Сколько компонент связности, состоящих из несгоревших вершин, будет в графе через i секунд после поджога? Причем необходимо найти ответ для каждого i от 0 до K, где K – время сгорания последней вершины, которая может сгореть.
Входные данные
В первой строке числа N, M и S (1 ≤ N, M ≤ 10^5, 1 ≤ S ≤ N) – количество вершин, количество рёбер и номер вершины поджога соответственно. Далее M строк описывают рёбра графа двумя числами a и b (1 ≤ a, b ≤ N) – концами очередного ребра. Граф может содержать кратные ребра и петли.
Выходные данные
В первой строке выведите число K – время сгорания последней вершины, которая может сгореть. Считайте, что вершина S подожжена в момент времени t=1 сек, и огонь распространяется между любыми двумя смежными вершинами за одну секунду. В следующей строке выведите К+1 чисел через пробел, где i-е число означает количество компонент связности, состоящих из вершин, которые еще не сгорели, по окончанию i секунд (0 ≤ i≤ K).
Пояснение: В первом примере в 0 секунду, то есть до поджигания, граф связный – количество компонент связности равно 1. По окончанию 1-й секунды сгорает вершина 2 и граф распадается на две компоненты связности (5) и (1, 3, 4). После 2-й секунды сгорают вершины 5, 1 и 3. Остаётся одна вершина 4, которая и образует компоненту связности. После 3-й секунды сгорает 4-я вершина, и компонент связности нет, так как все вершины сгорели.
Во втором примере в 0 секунду граф состоит из трех отдельных вершин – 3 компоненты связности. При поджоге первой вершины, она сгорает в 1-ю секунду и остаётся две компоненты связности. Поскольку больше никакие вершины не сгорят, то искомое время сгорания равно 1-й секунде.