Згоряння та компоненти зв'язності

Вхідні дані

У першому рядку числа $N$, $M$ та $S$ (1 \leq N, M \leq 10^5, 1 \leq S \leq N) — кількість вершин, кількість ребер та номер вершини підпалювання відповідно. Далі $M$ рядків описують ребра графа двома числами $a$ та $b$ (1 \leq a, b \leq N) — кінці чергового ребра. Граф може містити кратні ребра та петлі.

Вихідні дані

У першому рядку виведіть число $K$ — час згорання останньої вершини, яка може згоріти. Вважайте, що вершина $S$ підпалена у момент часу t = 1 сек, і вогонь поширюється між довільними двома суміжними вершинами за одну секунду. У наступному рядку виведіть K + 1 чисел через пробіл, де $i$-те число означає кількість компонент зв'язності, які складаються з вершин, що ще не згоріли, по завершенні $i$ секунд (0 \leq i \leq K).

Пояснення: У першому прикладі у $0$ секунду, тобто до підпалювання, граф зв'язний — кількість компонент зв'язності дорівнює $1$. По закінченні $1$-ї секунди згорає вершина $2$ і граф розпадається на дві компоненти зв'язності $(5)$ та (1, 3, 4). Після $2$-ї секунди згорають вершини $5$, $1$ та $3$. Залишається одна вершина $4$, яка й утворює компоненту зв'язності. Після $3$-ї секунди згорає $4$-та вершина, і компонент зв'язності немає, оскільки всі вершини згоріли.

У другому прикладі у $0$ секунду граф складається з трьох окремих вершин — $3$ компоненти зв'язності. При підпалюванні першої вершини вона згорає на $1$-й секунді й залишається дві компоненти зв'язності. Оскільки більше жодні вершини не згорять, то шуканий час згорання дорівнює $1$ секунді.

Приклади

5 5 2
1 2
1 3
1 4
3 4
3 5

3
1 2 1 0

3 0 1

1
3 2