#4427. [Nwerc2015] Cleaning Pipes清理管道

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有一个相当复杂的水资源运输系统。在Linköping周围的出水点有一些水井。这些水通过管道输送到其它地点。每条管道是从某一个水井到城市的某个位置的直线管道。

所有管道在地下的深度相同。因此，无论何时，两个管道相交时，它们会形成交点。幸运的是，管道系统正好是以满足两个管道有交点的方式建造。井不计入交点。任何数量的管道（包括零个与超过两个）都可以来源于每一个水井。

这些交点导致了一个问题，因为污垢（石灰和其它东西的混合物）往往会卡住交点，导致管道崩溃和坍塌，导致大型水槽孔的形成。这样的水槽孔对Linköping的学生有吸引的效果，使他们荒废学业，不受教育，这从长远来看将不只是导致管道系统的崩溃，还有社会的结构。因此，当务之急是管道定期清理。北欧提水再分配公司（NWERC） -负责Linköping的水管的 – 拥有充足的机器人车队才可以完成此任务。一个机器人可以在一条管道的开始位置被插入。然后，机器人通过管道一直到结束，并清除沿途所有交点。到达终点后，机器人转身并返回它开始的井。为了防止机器人互相碰撞，政府法规规定每当两个管相交，它们中的至多一个可以包含一个机器人。

由于整个水系统在被清洁时必须关闭（另一政府法规），则NWERC想迅速完成清洗，使用一批次清洁机器人，都必须在同一时间开始。

你的任务是验证是否可以做到这一点 - 即，是否能够把机器人同时插入管道中的一些，在不会有两个机器人相撞的危险下清洁所有交点。