Famous spaceship Alphaprise explores different planets in Alpha Centauri. Alphaprise is normally a wide spaceship however it needs to go through dense asteroid fields. To reduce the risk of being hit by an asteroid, top engineers of Alpha Centauri came together and modified Alphaprise adding “shapeshifting” feature -- it can change its formation to a shape like a long line segment. Given 2D schematic of Alphaprise, an example for shapeshifting is as follows:
![]() |
![]() |
Before shapeshifting | After shapeshifting |
As shown in the figure on the left, Alphaprise is composed of line segments with varying of lengths connected to each other at their endpoints. Endpoints are numbered from 1 to 10 in the figure. Line segments are foldable at connection points. Line segments have two sides; front and rear. Front side is shown with dashes whereas the rear side is solid. Alphaprise is shown after shapeshifting on the right side -- 4 is the front side and 5 is the rear side of the ship. During the shapeshifting, line segments folded in a way that all the front sides and rear sides of the line segments are in the right order. For instance, 9 is below 4 since 9 is the rear side and 4 is the front side of the segment.
Constraints:
-
Number of endpoints; 1 <= N <= 200
Input format:
- The first line is one integer M; number of line segments.
- Each of the next M lines has three integers x, y, and z where endpoint x is connected to y with length z (1 <= z <= 10) and x is the front side whereas y is the rear side. Endpoints are numbered from 1 to N.
Output format:
-
The output is the ordered list of endpoints after shapeshifting. The endpoints that are at the same point has to be on the same line in increasing order.
(Problem credit: Fatih Gelgi)
No editorial available for this problem.