Хвильовий обхід графа#1392
Нехай відстань від вершини до вершини визначається як мінімальна кількість ребер на шляху між та . Таким чином, відстань між та дорівнює , а відстань між будь-якими двома різними сусідніми вершинами дорівнює .
Хвильовий обхід графа з вершини — це послідовність вершин u_1, u_2, \ldots, u_r, яка задовольняє наступним умовам:
u_1 = v,
Кожна вершина графа, досяжна з , з'являється в цій послідовності хоча б один раз.
Кожна наступна вершина в послідовності знаходиться на відстані від вершини , яка не менша за відстань до попередньої вершини.
Дано зв'язний неорієнтований граф і вершину в ньому. Виведіть будь-який хвильовий обхід цього графа.
У першому рядку задано три цілі числа , і — кількість вершин, кількість ребер у графі та початкова вершина обходу (1 \leq N \leq 100, 0 \leq M \leq 10000, 1 \leq v \leq N). Наступні рядків містять по два числа u_i і v_i (1 \leq u_i, v_i \leq N), що означає існування ребра між вершинами u_i і v_i.
У першому рядку виведіть число — кількість вершин у знайденому хвильовому обході (1 \leq r \leq 10000; гарантується існування обходу, що задовольняє цим обмеженням). У другому рядку виведіть послідовність вершин u_1, u_2, \ldots, u_r, відокремлених пробілами.
Приклад 1