eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Волновой обход графа

Волновой обход графа

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Пусть расстояние от вершины u до вершины v - это минимальное количество рёебер в пути между u и v; так, расстояние между u и u - 0, а расстояние между любыми двумя различными соседними вершинами - 1.

Волновым обходом графа из вершины v назовём последовательность вершин u_1, u_2, ..., u_r такую, что:

  • u_1 = v,

  • Каждая вершина графа, достижимая из v, встречается в ней хотя бы один раз, и

  • Каждая следующая вершина последовательности удалена от вершины v не меньше, чем предыдущая.

Задан связный неориентированный граф и его вершина v. Выведите любой волновой обход этого графа.

Вхідні дані

В первой строке входного файла заданы числа N, M и v через пробел - количество вершин и рёебер в графе и начальная вершина обхода (1N100, 0M10000, 1vN). Следующие M строк содержат по два числа u_i и v_i через пробел (1u_i, v_iN); каждая такая строка означает, что в графе существует ребро между вершинами u_i и v_i.

Вихідні дані

В первой строке входного файла выведите число r - количество вершин в найденном волновом обходе (1r10000; гарантируется, что обход, удовлетворяющий этим ограничениям, существует). Во второй строке выведите сами числа u_1, u_2, ..., u_r через пробел.

Приклад

Вхідні дані #1
3 2 1
1 2
2 3
Вихідні дані #1
3
1 2 3