ЗАДАЧА B
Налево
| Имя входного файла: | left.in |
| Имя выходного файла: | left.out |
| Ограничение по времени: | 1 секунда |
| Ограничение по памяти: | 64 Мб |
Как известно, схема городских дорог задаётся графом на плоскости. Вершины этого графа – перекрёстки – точки с целочисленными координатами на плоскости, а рёбра – дороги. Будем считать, что между двумя перекрестками построено не более одной дороги и не существует дорог, соединяющих перекресток с самим собой. Ваша задача – найти такой путь от перекрёстка A до перекрёстка B, чтобы на всех перекрёстках поворачивать только налево. Поворотами налево считаются все повороты на угол не более 180 градусов против часовой стрелки. Путь с перекрёстка A можно начинать в любую сторону.
Входные данные
Первая строка входного файла содержит N и М – количество перекрестков и количество дорог (1<=N<=10000, 1<=M<=10000).Вторая строка содержит числа a и b – номера перекрестков A и B соответственно. Каждая из следующих N строк содержит пару целых чисел через пробел Xi и Yi – координаты перекрестка i. Последние M строк содержат 2M чисел, каждая пара чисел – номера перекрестков соединенных дорогой. Все координаты по модулю не превосходят 10000. На одном перекрестке не могут заканчиваться более 20 дорог.
Выходные данные
Если, сохраняя вышеуказанные правила невозможно добраться от перекрёстка A до перекрёстка B, то нужно вывести -1. Иначе нужно вывести количество дорог на этом пути, а затем номера соответствующих дорог в порядке объезда. Если по одной и той же дороге необходимо проехать 2 раза подряд номер этой дороги нужно вывести только один раз. Если есть несколько вариантов ответа, вывести любой.Пример
| left.in | left.out |
|---|---|
|
|