P2963 [USACO09NOV] Cow Rescue G

贝希被困在一个三角形的迷宫之中。这个迷宫有 $N$ 行（$1 \le N \le 1000000$）。比如下图是一个 $3$ 行的迷宫。 迷宫的第 $i$ 行有 $2i-1$ 个三角形，从左到右分别编号为 $(i, 1)$、$(i, 2)$ 等等。  贝希每次可以从一个三角形走到任意一个一个跟当前的三角形有邻边的三角形。 比如说，如果她目前处于三角形 $(3, 3)$，那么，她可以走到三角形 $(3, 2)$、$(3, 4)$ 和 $(4, 4)$。贝希每次需要一分钟的时间来移动到下一个三角形。  农夫约翰发现贝希被困了！于是她跟踪贝希的iPhone手机（可怜的触摸屏～），得知贝希目前处于三角形 $(S_i, S_j)$。 因为约翰对贝希有著无穷无尽的浓浓爱意，所以他希望贝希能尽可能快地回到他的身边。 在迷宫的三角形之中，有 $M$（$1 \le M \le 10000$）个是出口。在任何一个出口都可以让贝希逃离迷宫。一旦贝希进入一个作为出口的三角形，她用多一分钟就可以逃离这个迷宫。 找到一个可以让贝希逃离迷宫最小时间 $T$，并输出她应该从哪一个出口逃离迷宫，这个出口记为 $(\text{OUT}_i, \text{OUT}_j)$。 如果有多个出口同时需要时间 $T$，输出那个行的编号小的出口，如果仍然有多个出口，输出那个列的编号小的。

* 第 $1$ 行：两个空格分隔的整数：$N$ 和 $M$ * 第 $2$ 行：两个空格分隔的整数：$S_i$ 和 $S_j$ * 第 $3\dots M+2$ 行：第 $i+2$ 行包含两个空格分隔的整数，表示出口 $i$ 的三角形位置：$E_i$ 和 $E_j$

* 第1行：两个空格分隔的整数：$OUT_i$ 和 $OUT_j$ * 第2行：一个单独的整数：$T$