Bessie est piégée dans un labyrinthe triangulaire de $N$ rangées, $1 \le N \le 1,000,000$. Ci-dessous, trois rangées.

La rangée $i$ a $2*i-1$ triangles, numérotés depuis la gauche $(i,1)$, $(i,2)$, etc.

Elle peut passer dans les triangles partageant un côté, souvent trois. De $(3,3)$, vers $(3,2)$, $(3,4)$, $(4,4)$. Chaque passage prend une minute.

FJ apprend qu'elle est piégée et suit son iPhone pour connaître son départ vers la sortie ($Si,Sj$). Son amour est sans limites, et il veut qu'elle revienne au plus vite.

Il y a $M$ sorties dispersées, $1 \le M \le 10,000$, chacune permet de fuir. Après l'entrée dans un triangle de sortie, encore une minute suffit à quitter le labyrinthe.

Trouvez le temps minimal $T$ en minutes et la sortie optimale $(OUTi, OUTj)$. À égalité de $T$, prenez la plus petite rangée ; si elle est identique, la plus petite colonne.

Entrée

• Ligne $1$ : entiers $N$, $M$ séparés par un espace.

• Ligne $2$ : entiers $Si$, $Sj$ séparés par un espace.

• Lignes $3..M+2$ : ligne $i+2$, deux entiers séparés par un espace $Ei$, $Ej$, triangle de la sortie $i$.

Sortie

• Ligne $1$ : entiers $OUTi$, $OUTj$ séparés par un espace.

• Ligne $2$ : un entier $T$.

Exemples

Entrée 1

4 2
2 1
3 5
4 4

Sortie 1

4 4
4

Auteur du problème : Ye Wang, 2009