img
Czech ACM Student Chapter
Czech Technical University in Prague
Charles University in Prague
Technical University of Ostrava
acm
ˇ
Slovak University of Technology
University of Zilina
cz
Masaryk University
University of West Bohemia
CTU Open Contest 2017
Treetop Walkway
walkway.c, walkway.cpp, walkway.c11, Walkway.java, walkway.py
The amusement park is a real landscape park which means that there are significant portions
of forest standing among the attractions. A huge treetop walkway allows the visitors to explore
the unusual world of tree canopies and enjoy spectacular views of hills and lakes in the region.
The walkway consists of wooden platforms installed close to the treetops in different heights
above the ground and connected by narrow wooden paths. Each path connects exactly two
platforms. Number of paths connected to one platform may vary. Each platform can be reached
from any other platform without leaving the walkway.
To improve the safety standards and to alleviate occasional bottleneck problems in some parts of
the walkway, the management decided to make all paths strictly one-way for the visitors. After
each path was assigned a direction, someone found out that a connection problem appeared. It
turned out that there may be platforms which would not be accessible from some other platforms
if the visitors followed only prescribed path directions and did not leave the walkway. As the
direction choice was made by the management on the basis of various "aesthetical and functional
considerations", changing the already-assigned directions is not an option.
To fix the problem, it was decided to build additional one-way paths. Those will connect selected
platforms in such manner that any platform will be accessible from any other platform without
leaving the walkway. All other properties of the walkway will remain unchanged. They are not
going to build any new platform.
They want to minimize the number of new paths by careful selection of the platforms to be
connected and also by correct direction settings of the new paths.
Input Specification
There are more test cases. Each case starts with a line containing two integers N , M separated
by space (1 N 105, 0 M 2 · 105). N is the number of treetop platforms, M is number
of current treetop paths. The platforms are labeled by integers 1, 2, . . . , N . Next, there are M
lines, each of them specifies one treetop path and its direction. The line contains the labels of
two different platforms separated by space, the planned direction of the path is from the first
platform on the line to the second one. All paths in the input are unique. In the final walkway
arrangement, there will be at most two paths connecting any two given platforms A and B, one
in the direction A B and another in the direction B A.
Output Specification
For each test case, first print a single line with a single integer R specifying the minimum
number of additional treetop paths which ensure the reachability of any platform from any
other platform. On the next R lines, print all the new paths in the same format as in the input.
If there are more solutions of the problem, any of them will be accepted.
Sample Input
5
6
1
2
2
3
3
1
2
4
4
5
5
4
4
3
2
1
3
1
4
1
6
5
1
4
1
5
1
6
2
4
3
4
Output for Sample Input
1
4
1
3
4
2
3
4
1
3
3
4
1
6
2
5
3