rute

Rute maritime

== include(page="template/taskheader" task_id="rute") ==

Poveste si cerinta...

Un turist roman a plecat intr-o excursie pe Marea Mediterana. El a ajuns intr-unul dintre orasele de pe una din cele $3$ insule pe care doreste sa le viziteze. Fiecare insula are exact $N$ orase si toate sunt porturi. Turistul doreste sa isi inceapa calatoria din orasul in care se afla, sa viziteze toate celelalte $3*N-1$ orase exact o data si apoi sa se intoarca in orasul de unde si-a inceput calatoria, pentru a pleca dupa aceea inapoi spre casa.
 
Din pacate, pe fiecare din cele $3$ insule traiesc triburi de canibali, astfel incat este interzis de catre autoritati sa se calatoreasca direct intre $2$ orase de pe aceeasi insula. Din fericire, exista rute maritime intre orice pereche de orase care nu se afla pe aceeasi insula. Nu exista rute maritime intre $2$ orase de pe aceeasi insula.
 
Turistul vrea sa stie in cate moduri isi poate planifica calatoria pe cele $3$ insule.

h2. Date de intrare

...

Fisierul de intrare $rute.in$ contine un singur numar intreg $N$, reprezentand numarul de orase de pe fiecare din cele $3$ insule.

h2. Date de iesire

...

In fisierul de iesire $rute.out$ veti afisa numarul de posibilitati de planificare a calatoriei. $2$ calatorii se considera identice daca secventa de $3*N$ orase vizitate este identica sau daca secventa oraselor vizitate in cadrul primei calatorii este identica cu secventa oraselor vizitate in a doua calatorie, dar citita invers (de exemplu, daca fiecare insula ar avea un singur oras, numerotat cu numarul insulei, calatoriile $1-2-3-1$ si $1-3-2-1$ ar fi identice).

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 30$

h2. Exemplu
table(example). |_. rute.in |_. rute.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicatie
 
...

|2|16|

== include(page="template/taskfooter" task_id="rute") ==

2299