Алгоритмы на графах

Задача

Задан неориентированный граф. Вершины графа - точки на плоскости, заданы координатами (пара целых чисел). Рёбра заданы парами вершин. Например, строка

x1 y1 x2 y2

задаёт ребро, соединяющее вершину с координатами (x1,y1) и вершину (x2,y2).

Какой алгоритм применять:

• Если ваша фамилия начинается с "А"-"Н", то нужно применять поиск в ширину.
• Иначе (фамилия начинается с "О"-"Я"), то поиск в глубину.

Формат входных данных

Файл содержит m+1 строк, где m - количество рёбер графа.

В первой строке - одно число: m (=количество рёбер).

Далее, в каждой последующей строке указано одно ребро в виде двух пар координат вершин.

Формат выходных данных

В первой строке количество рёбер, входящих в цикл.

В следующих строках описание цикла в виде последовательности пар координат. В каждой строке координаты одной вершины. Вершины должны быть перечислены в том порядке, в котором они входят в цикл.

Пример входного и соответствующего выходного файла приложен к заданию.

За полностью сданное задание: 12 баллов.

За успешную сдачу до раннего срока (18.10.25 включительно): +2 балла.