Bessie mắc kẹt mê cung tam giác $N$ hàng, $1 \le N \le 1,000,000$. Dưới là ba hàng.

Hàng $i$ có $2*i-1$ tam giác, từ trái $(i,1)$, $(i,2)$, v.v.

Đi tới tam giác chung cạnh, thường ba. Từ $(3,3)$ tới $(3,2)$, $(3,4)$, $(4,4)$. Mỗi lần đi mất một phút.

FJ biết cô mắc kẹt và theo iPhone biết bắt đầu tìm lối ra tại ($Si,Sj$). Tình yêu vô hạn, ông muốn cô về nhanh nhất.

Có $M$ lối ra khắp nơi, $1 \le M \le 10,000$, lối nào cũng thoát được. Vào tam giác lối ra rồi chỉ thêm một phút để ra mê cung.

Tìm thời gian nhỏ nhất $T$ phút và lối ra tối ưu $(OUTi, OUTj)$. Nhiều lối cùng $T$ thì hàng nhỏ nhất; hàng bằng nhau thì cột nhỏ hơn.

Dữ liệu vào

• Dòng $1$: số nguyên $N$, $M$ cách bằng khoảng trắng.

• Dòng $2$: số nguyên $Si$, $Sj$ cách bằng khoảng trắng.

• Các dòng $3..M+2$: dòng $i+2$, hai số nguyên cách bằng khoảng trắng $Ei$, $Ej$, vị trí tam giác lối ra $i$.

Dữ liệu ra

• Dòng $1$: số nguyên $OUTi$, $OUTj$ cách bằng khoảng trắng.

• Dòng $2$: một số nguyên $T$.

Ví dụ

Dữ liệu vào 1

4 2
2 1
3 5
4 4

Dữ liệu ra 1

4 4
4

Tác giả bài toán: Ye Wang, 2009