eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Jill and Phil`s Palindromic Peregrinations

Jill and Phil`s Palindromic Peregrinations

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Jill and her friend Phil are going to ride bikes around Warsaw to do the "tourist thing" – that is, see the sights. Not being familiar with Warsaw, they plan to travel routes that are somewhat simple to remember. Each intersection encountered in their trips will have exactly four roads by which the intersection can be exited, one at each of the compass points north, east south, and west. They will leave each intersection on the road that is relatively left (L), right (R), or forward (F) of the road on which they enter the intersection (which is also conveniently at one of the four compass points). They won’t pass through any intersection more than twice. And the sequence of letters (from the set F, L and R) describing their route – that is, their action at each intersection – forms a palindrome!

For example, consider the map shown to the right, with north at the top of the map. Each of the numbered circles represents an intersection; each has four roads connected to it, although some may be like the one going east from intersection 3 – a dead end. The circle labeled "x" is Jill and Phil's hotel, from which all their routes will start by going Forward. The lines (edges) between the circles represent roads.

One palindromic route from the hotel can be specified as FLRLF: forward from the hotel to 3, then left from 3 to 2, then right from 2 to 1, then left from 1 to 3, and finally forward from 3 to the hotel. This route is shown with the directed edges on the map. Another palindromic route is FLLFFLLF. This route goes from the hotel to intersections 3, 2, 4, 4 again, 2, 1, 3, and finally back to the hotel.

Given a map, find all the palindromic routes that Jill and Phil might take.

Вхідні дані

The input contains several maps followed by a line containing a single zero.

The first line of input for each map gives the number of intersections, N, which will be no larger than 15. The line then has the intersection number (1..N) immediately followed by the capital letter compass point ('N', 'E', 'S', or 'W') where the road Forward from the hotel will take Jill and Phil.

Then there are N lines, one for each intersection (numbered 1 to N). The four space-separated fields on the K–th of these lines indicate the intersections to which the four roads from intersection K are connected; the fields correspond to the roads leaving the north, east, south, and west of intersection K, respectively. Each field contains one of the following:

  • an intersection number L immediately followed by one of the capital letter compass points 'N', 'E', 'S', or 'W'; this indicates that the corresponding road leaving intersection K connects to intersection L at the specified compass point.

  • 0; this indicates the corresponding road is a dead-end on which travel is not possible.

  • –1; this marks the road that leads to the hotel. There will only be one such road in the map.

Вихідні дані

For each input map, display the map number and each of the possible palindromic routes in lexicographic order. Display the message "NO ROUTES" if there are no palindromic routes possible. Follow the format of the sample output.

Приклад

Вхідні дані #1
4 3S
1E    1N    2N    3N
1S    3W    4N    4W
1W    0    -1     2E
2S    4S    4E    2W
2 1S
1E    1N    -1    2E
0     1W     0    0
2 1S
2S 2E -1 0
0 1E 1N 0
0
Вихідні дані #1
Map 1:
   FFLFF
   FLFFFFLF
   FLFLFLF
   FLFRRFLF
   FLLFFLLF
   FLLLLLLF
   FLLRLLF
   FLRLF
Map 2:
   FRF
Map 3:
   NO ROUTES
Джерело ACM North Central North America Regional Programming Contest, November 12, 2011