Zadání - The Deep Caves

National Underworld Association (NUA) is a huge organization which manages and organizes visitor tours in the caves of the country biggest karst region spanning hundreds of square kilometers. Recently they have encountered some tours planning problems which we are expected to help them with. Let us first describe the overall situation in the caves.

From the point of view of the visitor to the caves there are two basic structural elements of the cave complex: Halls and passages. Passages are typically dark narrow winding corridors often with unpleasantly low ceilings and sharp rock edges and there is not too much to be seen there. A hall is a space where a group of people can stand upright and admire dazzling creations of mysterious subterranean geology. All halls are connected by passages. When visitors travel from one hall to another hall they must always go (or crawl) through some passage, no two connected halls are so close that there would be no passage between them. Also no two passages cross or meet outside a hall, that is, one cannot move from one passage to another without visiting a hall into or from which they both lead.

Because of difficult movement in them, all passages are kept strictly one directional to avoid jams and ensure maximum security of the visitors.

Up until this year the regime in the caves has been like follows. There are three separate areas in the cave complex, let us call them area A, B and C. Each area is served by one separate tour through it. No two of these tours share any hall or a passage. All three tours are circular, the visitors start their tour in a particular hall in the area and then move through passages and halls never visiting any hall twice except for the starting hall where the tour also ends. This organization was left unchanged and additional options specified bellow were established.

During this year the exploration of previously unknown area of the cave complex has been completed. The letter D is reserved for this area, because D is the deepest one. New exciting tours through D were created. The area D also consists of interconnected halls and passages and the number of its passages is the same as the number of its halls. These halls and passages in D form a natural circle so one could expect that the tour scheme through D might be the same as in areas A, B or C. But because D is the deepest area this is not the case. Due to the safety measures and complicated access to the caves in D there are exactly two halls R1 and R2 in D where the tours through D start. Exactly two passages lead from the hall R1 into its two other neighbour halls in D. The same situation is with R2. All passages of area D are one directional too, so consequently R1 and R2 cannot be neighbouring halls connected by a single passage. As you can easily see it is not possible to travel from R1 to R2 or vice versa and thus there are two other halls L1 and L2 where the all tours through D end. To sum it up, there are four tours through D: From R1 to L1, from R1 to L2, from R2 to L1 and from R2 to to L2 . There is no passage from hall L1 or L2 to other hall of D, visitors are taken from there directly to the surface via artificial shafts.

Moreover, to expand the future tour possibilities three different halls in D were chosen and three new passages were prepared. The three chosen halls in D are marked a, b, c and for any of them is not important whether it is a tour starting (R1 or R2) or tour ending (L1 or L2) or other hall in D. The additional passages are these: Passage Pa leads from a to some hall of tour in A, passage Pb leads from b to some hall of tour in B, Passage Pc leads from c to some hall of tour in C. The passages Pa, Pb, Pc and their corresponding starting halls a, b, c currently do not serve to expand or alter any of the existing tours, their incorporation in additional tours is planned for the next year.

Unfortunately, the majority of the directory board of NUA thinks that halls R1, R2, L1, L2 and halls a, b, c were chosen too hastily without reliable speleological analysis and that for the future it would be probably better to choose them differently according to the updated research results of the caves. The board would like to evaluate all different choices of R1, R2, L1, L2, a, b, c, they call them configurations, and eventually install and exploit the best one of them. If the number of configurations turns up to be too large, some other decision strategy will be adopted.

Thus the number of possible configurations should be calculated in advance and it is the goal of this problem.

For us it remains to define what the board understands by configuration and what are different configurations. Let us suppose that there are in total N halls in areas A, B, C, and D together. The halls can be labeled by numbers 0, 1, …, N− 1 in any order. Each passage in a tour then can be identified by the label of its start hall followed by the label of its end hall. The configuration is simply a list of all passages identifications presented in arbitrary order. The passages Pa, Pb, Pc are described in the same format and are included in the list. Thus the list contains exactly N+3 items. The configuration should preserve the directions of the passages in the A, B, C areas and the directions of passages Pa, Pb, Pc in the sense that their respective end halls should remain in areas A, B, C. It is supposed that a passage can be constructed from any hall of area D to any hall of areas A, B, C, so the start halls of passages Pa, Pb, Pc may vary arbitrarily in different configurations.

Two configurations X and Y (or two lists of one directional passages, if you will) are considered to be equivalent if the halls in one of the lists can be relabeled and then the list reordered in such way that it matches exactly the other list. Let us define this notion exactly. Configuration X is a sequence of ordered tuples

(x1,s, x1,e ), (x2,s, x2,e ), …, (xN+3,s, xN+3,e ), where xi,s ≠ xi,e and 1 ≤ xi,s, xi,e ≤ N for 1 ≤ i ≤ N+3.

Configuration Y is a sequence of ordered tuples

(y1,s, y1,e ), (y2,s, y2,e ), …, (yN+3,s, yN+3,e ), where yi,s ≠ yi,e and 1 ≤ yi,s, yi,e ≤ N for 1 ≤ i ≤ N+3.

The tuple (xi,s, xi,e), resp (yi,s, yi,e) represents one directional passage from hall xi,s to hall xi,e, resp. from hall yi,s to hall yi,e.

Configurations X and Y are said to be equivalent if there exist two bijective functions

f: {0, 1, …, N−1} → {0, 1, …, N−1},

g: {1, 2, …, N+3} → {1, 2, …, N+3},

such that for each (1 ≤ i ≤ N+3) holds

(xg(i),s, xg(i),e) = (f(yi,s), f(yi,e)).

Two configurations are different if and only if they are not equivalent.

Input consists of the description of the configuration which is currently implemented in the caves. As stated above it includes one way passages in areas A, B, C, D and three additional passages Pa, Pb, Pc. First input line contains the number P of passages in the configuration. Each of the next P lines contains description of a single one way passage in the current configuration. The line contains the label of the start hall and then the label of the end hall of the passage. The labels are separated by a space. Value P (number of passages) can be any integer between 13 and 60000.

The output contains a single line with a number of possible different configurations as they are defined above. The currently implemented configuration (which is the input) is included in the number.

16
7 10
12 1
7 0
5 9
3 8
11 12
6 10
1 11
6 0
8 4
7 12
4 3
0 9
6 3
2 5
9 2

2

20
4 6
10 5
5 15
8 16
14 9
2 12
14 6
3 2
15 7
0 10
11 4
13 3
0 3
12 13
16 15
0 9
7 1
14 5
1 8
6 11

60

24
15 16
10 3
3 12
12 11
14 7
7 18
7 8
5 6
19 0
6 1
11 4
14 13
13 10
20 19
16 13
17 9
4 10
8 17
14 19
1 8
9 5
2 20
15 18
0 2

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout a stderr is available to him/her.

pal-cave-task03_datapub.zip