eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Очистка труб

Очистка труб

Ліміт часу 1 секунда
Ліміт використання пам'яті 122 MiB

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

Все трубы находятся на одной и той же глубине под землей. Поэтому, когда две трубы пересекаются, они образуют пересечение. К счастью, трубопроводная система была построена таким образом, что на каждом таком пересечении встречаются ровно две трубы. Колодцы не считаются пересечениями. Любое количество труб (включая ноль или более двух) может примыкать к каждой скважине.

Перекрестки создают проблему, поскольку грязь (смесь извести и других элементов "остается") имеет тенденцию застревать там. Эта грязь заставляет трубы разлагаться и разрушаться, что приводит к образованию крупных раковинных отверстий. Такие раковины имеют эффект гипноза на студентов в Линчёпинге, заставляя их пренебрегать своими исследованиями и оставаться необразованными, что в конечном итоге приведет к краху не только трубопроводной системы, но и самой структуры общества. Поэтому необходимо регулярно чистить трубы. Компания Nordic Water Extraction and Redistribution Company (NWERC), которая отвечает за водопроводные трубы Линчёпинга, располагает достаточным парком роботов для выполнения этой задачи. Робот может быть вставлен в скважину, где начинается труба. Затем робот проходит через трубу до конца и очищает все перекрестки на пути. Подойдя к концу, робот оборачивается и возвращается обратно в колодец, откуда он начинал свою работу. В целях предотвращения столкновений роботов в правительственных постановлениях предусматривается, что при пересечении двух труб максимум только по одной из них может проходить робот.

Так как вся система водоснабжения должна быть отключена во время очистки (другое правительственное регулирование), NWERC хотела бы быстро все почистить, используя одну партию чистящих роботов, которые начинают работу в одно и то же время.

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

Вхідні дані

Состоит из:

  • строка содержит два числа w (1w1000) - число колодцев и p (1p1000) - число труб;

  • w строк, i-ая из которых содержит два целых числа x[i] и y[i] (-10000x[i], y[i]10000) - позиция колодца номер i (колодцы пронумерованы от 1 до w);

  • p строк с тремя целыми числами s (1sw) - номер скважины в которой начинается труба, и x и y (-10000x, y10000) - положение где завершается труба.

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

Вихідні дані

Если можно почистить все перекрестки, то вывести "possible". Иначе вывести "impossible".

Приклад

Вхідні дані #1
3 3
0 0
0 2
2 0
1 2 3
2 2 2
3 0 3
Вихідні дані #1
impossible
Вхідні дані #2
2 3
0 0
0 10
1 5 15
1 2 15
2 10 10
Вихідні дані #2
possible
Джерело 2015 ACM North Western European Regional Contest (NWERC), Ноябрь 30, Задача C