Bessie steckt in einem Dreieckslabyrinth mit $N$ Reihen, $1 \le N \le 1,000,000$. Unten sind drei Reihen gezeigt.

Reihe $i$ hat $2*i-1$ Dreiecke, von links $(i,1)$, $(i,2)$ usw.

Sie kann zu Dreiecken mit gemeinsamer Kante gehen, oft drei. Von $(3,3)$ nach $(3,2)$, $(3,4)$, $(4,4)$. Ein Schritt dauert eine Minute.

FJ erfährt ihre Lage und verfolgt ihr iPhone: Der Weg zum Ausgang beginnt bei ($Si,Sj$). Seine Liebe ist grenzenlos, er will sie schnellstmöglich zurück.

Es gibt $M$ verteilte Ausgänge, $1 \le M \le 10,000$, jeder ermöglicht Flucht. Nach Betreten eines Ausgangsdreiecks braucht sie noch eine Minute nach draußen.

Finde die minimale Zeit $T$ Minuten und den optimalen Ausgang $(OUTi, OUTj)$. Bei gleichen $T$ kleinste Reihe, bei gleicher Reihe kleinere Spalte.

Eingabe

• Zeile $1$: ganze Zahlen $N$, $M$ durch Leerzeichen.

• Zeile $2$: ganze Zahlen $Si$, $Sj$ durch Leerzeichen.

• Zeilen $3..M+2$: Zeile $i+2$, zwei ganze Zahlen durch Leerzeichen $Ei$, $Ej$, Dreieck des Ausgangs $i$.

Ausgabe

• Zeile $1$: ganze Zahlen $OUTi$, $OUTj$ durch Leerzeichen.

• Zeile $2$: eine ganze Zahl $T$.

Beispiele

Eingabe 1

4 2
2 1
3 5
4 4

Ausgabe 1

4 4
4

Aufgabenautor: Ye Wang, 2009