Згоряння та компоненти зв`язності
Одного разу Ви спостерігали, як згорає граф – це дуже цікавий процес. Спочатку граф горить, але залишається зв'язним, потім у якийсь момент він починає розпадатись на окремі зв'язні шматки, а через деякий час ці окремі шматки зовсім згорають і щезають.
Вам так сподобалось дивитись на горіння графа, що Ви вирішили промоделювати його на своєму комп'ютері. Для цього Вам необхідно відповісти на таке питання: Скільки компонент зв'язності, які складаються з незгорівших вершин, буде у графі через 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-й секунді.