[Nwerc2015] Cleaning Pipes清理管道

时间限制:5s    【提交】    空间限制:1024MB


Linköping has a quite complex water transport system. Around Linköping there are several wells from which water is drawn. The water is then transported to other locations using pipes. Each pipe is a straight canal from one of the wells to some location in the city.
All the pipes are at the same depth under ground. Therefore, whenever two pipes cross, they form an intersection. Luckily the pipe system was constructed in such a way that exactly two pipes meet at each such intersection. The wells do not count as intersections. Any number of pipes (including zero or more than two) may originate at each well.
The intersections pose a problem, since dirt (a mixture of lime and other “remains”) tends to get stuck there. This dirt causes the pipes to degrade and collapse, leading to the formation of large sink holes. Such sink holes have a mesmerising effect on the students in Linköping, causing them to neglect their studies and remain uneducated, which in the long run will lead to a collapse of not just the pipe system but of the very fabric of society. Therefore it is imperative that the pipes are regularly cleaned. The Nordic Water Extraction and Redistribution Company (NWERC) – which is in charge of Linköping’s waterpipes – has an ample fleet of robots to perform this task. A robot can be inserted into a pipe at the well where the pipe begins. The robot then goes through the pipe all the way to its end and cleans all intersections along the way. After reaching the end, the robot turns around and returns back to the well where it started. In order to prevent robot collisions, government regulations stipulate that whenever two pipes intersect, at most one of them may contain a robot.
Since the whole water system has to be shut down while it is being cleaned (another government regulation), the NWERC would like to do the cleaning quickly, by using a single batch of cleaning robots, all started at the same time.
Your task is to verify whether this can be done – i.e., whether we can simultaneously insert robots into a subset of the pipes in such a way that the robots will clean all intersections and there will be no risk of two robots colliding.
这些交点导致了一个问题,因为污垢(石灰和其它东西的混合物)往往会卡住交点,导致管道崩溃和坍塌,导致大型水槽孔的形成。这样的水槽孔对Linköping的学生有吸引的效果,使他们荒废学业,不受教育,这从长远来看将不只是导致管道系统的崩溃,还有社会的结构。因此,当务之急是管道定期清理。北欧提水再分配公司(NWERC) -负责Linköping的水管的 – 拥有充足的机器人车队才可以完成此任务。一个机器人可以在一条管道的开始位置被插入。然后,机器人通过管道一直到结束,并清除沿途所有交点。到达终点后,机器人转身并返回它开始的井。为了防止机器人互相碰撞,政府法规规定每当两个管相交,它们中的至多一个可以包含一个机器人。
你的任务是验证是否可以做到这一点 - 即,是否能够把机器人同时插入管道中的一些,在不会有两个机器人相撞的危险下清洁所有交点。


The input consists of:
one line with two integers ww (1≤w≤10001≤w≤1000), the number of wells, and pp (1≤p≤10001≤p≤1000), the number of pipes;
ww lines, the iith of which contains two integers xixi and yiyi (−10000≤x,y≤10000−10000≤x,y≤10000), the position of well number ii (the wells are numbered from 11 to ww);
pp lines each with three integers ss (1≤s≤w1≤s≤w), the well at which the pipe starts, and xx and yy (−10000≤x,y≤10000−10000≤x,y≤10000), the position at which the pipe ends.
Each pipe will contain exactly one well, the one at which it starts. Any point shared by more than two pipes will be a well. Any two pipes share at most one common point. The common point of two pipes may be the endpoint of one or both of them. All pipes have positive length.


If it is possible to clean all intersections as described above, output “possible”. Otherwise, output “impossible”.


Sample input 1
3 3
0 0
0 2
2 0
1 2 3
2 2 2
3 0 3
Sample input 2
2 3
0 0
0 10
1 5 15
1 2 15
2 10 10


Sample output 1

Sample output 2