X Olympiad in Informatics 2002/2003
Author: Tomasz Waleń
Byteotia lies on a peninsula. As far back as from the times of king Bitol railways have been being the basic means of transport in Byteotia. King Bitol has a superspeed railway line built. The line connects eastern and western coasts of the peninsula, runs through all the towns of Byteotia and thus determines their enumeration: the first town on the line has the number 1 and the last has n. The town number 1 lies on the western coast and the town number n lies on the eastern coast.
Fig. 1. The Byteotian railway line
Recently, thanks to the minister Byterowicz, the economy of Byteotia has developed very rapidly and the present-day transport network needs to be quickly modernised. King Byteol has given orders for many motorways to be constructed (in the framework of the next 23-year plan). Each of the motorways is to join directly two chosen towns of Byteotia. As each motorway is going to be constructed by a different government agency and on each of the motorways different vignettes are going to be obligatory, it has been decided that the motorways must not cross neither one another nor the railway line. Thus the only solution is to construct each motorway to the north or to the south of the railway line. Figure 2 shows a sample arrangement of motorways (presented as dotted arcs, while the railway line is drawn as the solid line).
Fig.2. Sample arrangement of motorways joining towns:
1-2, 1-3, 2-4, 5-7, 4-8, 7-8, 6-8
His Majesty King Byteol has already decided which pairs of towns are to be directly connected by motorways. Your task is to determine which motorways should lie to the north from the railway line, and which to the south. Remember, however, that the motorways must not cross neither one another nor the railway line.
The memory limit for this task is 32 MB.
8 7 1 2 1 3 2 4 5 7 4 8 7 8 6 8a correct answer is in the following output:
N N S S S N N