Очищення труб#7864
Лінчепінг має досить складну систему водопостачання. Навколо міста розташовані кілька колодязів, з яких видобувається вода. Вода транспортується до різних місць через труби. Кожна труба є прямим каналом від одного з колодязів до певного місця в місті.
Всі труби прокладені на одній глибині під землею. Тому, коли дві труби перетинаються, утворюється перехрестя. На щастя, система трубопроводів спроектована так, що в кожному перехресті зустрічаються рівно дві труби. Колодязі не вважаються перехрестями. До кожного колодязя може прилягати будь-яка кількість труб (включаючи нуль або більше двох).
Перехрестя створюють проблему, оскільки бруд (суміш вапна та інших елементів) має тенденцію накопичуватися там. Цей бруд призводить до розкладання і руйнування труб, що викликає утворення великих провалів. Такі провали мають гіпнотичний ефект на студентів у Лінчепінгу, змушуючи їх нехтувати навчанням, що врешті-решт може призвести до краху не лише трубопровідної системи, але й суспільства в цілому. Тому необхідно регулярно чистити труби. Компанія Nordic Water Extraction and Redistribution Company (NWERC), яка відповідає за водопровідні труби Лінчепінга, має достатньо роботів для виконання цього завдання. Робот може бути вставлений у колодязь, звідки починається труба. Потім він проходить через трубу до кінця, очищаючи всі перехрестя на шляху. Досягнувши кінця, робот повертається назад у колодязь, звідки почав. Щоб уникнути зіткнень роботів, урядові постанови передбачають, що на перехресті двох труб одночасно може перебувати робот лише в одній з них.
Оскільки вся система водопостачання повинна бути відключена під час очищення (згідно з урядовими регулюваннями), NWERC хоче швидко виконати очищення, використовуючи одну партію роботів, які починають роботу одночасно.
Вам потрібно визначити, чи можливо це зробити, тобто чи можна одночасно запустити роботів у певний набір труб так, щоб вони очистили всі перехрестя без ризику зіткнення.
Складаються з:
рядка, що містить два числа (1 \le w \le 1000) - кількість колодязів, і (1 \le p \le 1000) - кількість труб;
рядків, де -ий рядок містить два цілі числа x_i і y_i (-10000 \le x_i, y_i \le 10000) - координати колодязя номер (колодязі пронумеровані від до );
рядків з трьома цілими числами (1 \le s \le w) - номер колодязя, з якого починається труба, і і (-10000 \le x, y \le 10000) - координати кінця труби.
Кожна труба починається з одного колодязя. Будь-яка точка, до якої прилягає більше ніж дві труби, є колодязем. Будь-які дві труби мають не більше однієї спільної точки. Спільна точка двох труб може бути кінцевою точкою однієї або обох з них. Всі труби мають позитивну довжину.
Якщо можливо почистити всі перехрестя, виведіть possible. Інакше виведіть impossible.
Приклад 1
Приклад 2