Nach Vorbild der Erbauer amerikanischer Interstate-Autobahnen führen Kühe Weidenstraßennummern ein. $N$ Weiden ($2\le N\le25$) sind $1\ldots N$, jeder Weg hat eindeutige Nummer $1\ldots2000$, etwa I-9 und I-16.

Beispiel: Weiden 1,2,3,4 verbunden durch I-3,I-6,I-9,I-16:

                  4--<I-6>--2
                 /         /
             <I-16>     <I-9>   
               /         /
              1--<I-3>--3

Bessie geht gern auf dem neuen Netz von 1 zu 2, ohne eine Weide doppelt zu besuchen: 1-4-2 und 1-3-2 im Beispiel.

Über Jahre entwickelte sie erstaunliche Mathematik und sucht den größten gemeinsamen Teiler (GCF) der Wegnummern. 1-4-2 nutzt I-16,I-6, GCF 2: 2 teilt 16 und 6, kein größeres Ganzes beide.

Tag für Tag geht sie alle Wege $1\to2$ und merkt GCF. Nachdem sie alle möglichen Wege jeweils einmal gegangen ist, berechnet sie deren kleinstes gemeinsames Vielfaches (LCM). Beispiel 2,3: $\gcd(6,16)=2$, $\gcd(3,9)=3$, LCM 6.

Große Netze ermüden, aber sie will LCM jeder Karte. Berechne es.

Eingabe

• Zeile 1: $N$.
• Zeilen $2..N+1$: $N$ Zeilen symmetrische Matrix. Zeile $L$: $N$ Ganzzahlen mit Leerzeichen, Verbindungen von $L-1$, erste Wegnummer zu 1, zweite zu 2 usw. $A$ zu $B$ impliziert Rückrichtung. Ohne Weg 0.

Ausgabe

Eine Zeile, Ganzzahl LCM aller GCF der Wege $1\to2$, garantiert höchstens 100 Ziffern.

Beispiele

Eingabe 1

4
0 0 3 16
0 0 9 6
3 9 0 0 
16 6 0 0

Ausgabe 1

6

Aufgabenautor: Vlad Novakovski, 2002