Məsələlər
Волновой обход графа
Волновой обход графа
Пусть \textit{расстояние} от вершины \textbf{u} до вершины \textbf{v} - это минимальное количество рёебер в пути между \textbf{u} и \textbf{v}; так, расстояние между \textbf{u} и \textbf{u} - \textbf{0}, а расстояние между любыми двумя различными соседними вершинами - \textbf{1}.
\textit{Волновым обходом графа} из вершины \textbf{v} назовём последовательность вершин \textbf{u_1}, \textbf{u_2}, ..., \textbf{u_r} такую, что:
\begin{itemize}
\item \textbf{u_1} = \textbf{v},
\item Каждая вершина графа, достижимая из \textbf{v}, встречается в ней хотя бы один раз, и
\item Каждая следующая вершина последовательности удалена от вершины \textbf{v} не меньше, чем предыдущая.
\end{itemize}
Задан связный неориентированный граф и его вершина \textbf{v}. Выведите любой волновой обход этого графа.
\InputFile
В первой строке входного файла заданы числа \textbf{N}, \textbf{M} и \textbf{v} через пробел - количество вершин и рёебер в графе и начальная вершина обхода (\textbf{1} ≤ \textbf{N} ≤ \textbf{100}, \textbf{0} ≤ \textbf{M} ≤ \textbf{10000}, \textbf{1} ≤ \textbf{v} ≤ \textbf{N}). Следующие \textbf{M} строк содержат по два числа \textbf{u_i} и \textbf{v_i} через пробел (\textbf{1} ≤ \textbf{u_i}, \textbf{v_i} ≤ \textbf{N}); каждая такая строка означает, что в графе существует ребро между вершинами \textbf{u_i} и \textbf{v_i}.
\OutputFile
В первой строке входного файла выведите число \textbf{r} - количество вершин в найденном волновом обходе (\textbf{1} ≤ \textbf{r} ≤ \textbf{10000}; гарантируется, что обход, удовлетворяющий этим ограничениям, существует). Во второй строке выведите сами числа \textbf{u_1}, \textbf{u_2}, ..., \textbf{u_r} через пробел.
Giriş verilənləri #1
3 2 1 1 2 2 3
Çıxış verilənləri #1
3 1 2 3