E. Петя болон Тэгш өнцөгт

хугацааны хязгаарлалт 5 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бяцхан Петя тэгш өнцөгтөөр тоглох дуртай. Ээж нь Петяд $n × m$ хэсэгт хуваагдсан ($n$ мөр, $m$ баганатай) тэгш өнцөгт авчирж өгжээ. Петя 2 ялгаатай нүдийг нь тэмдэглээд дараах бодлогыг бодож байна:

_Энгийн зам_ гэж 2 нүдийг холбосон $a_1, a_2, ... , a_k$ ялгаатай нүдүүдийн дарааллыг хэлнэ. Энд $a_1$ болон $a_k$ нь тэмдэглэсэн нүдүүд байна. Мөн $a_i$ болон $a_{i+1}$ нь хөрш нүдүүд байна. Энэ замын уртыг $k$ гэж тэмдэглэе (дарааллын урт).

Петягийн даалгавар бол хамгийн урт энгийн замыг олох. Түүнд тусла.

Оролт

Эхний мөрөнд тэгш өнцөгтийн урт өргөн болох $n, m$ ($4 ≤ n, m ≤ 1000$) тоонууд өгөгдөнө. Хоёрдахь мөрөнд эхний тэмдэглэсэн нүдний байрлал $x_1 \ y_1$ өгөдөнө. Дараагийн мөрөнд хоёрдох тэмдэглэсэн нүдний байрлал болох $x_2 \ y_2$ өгөгдөнө. ($1 < x_1, x_2 < n$, $1 < y_1, y_2 < m$, $x_1 ≠ x_2$, $y_1 ≠ y_2$).

Тэмдэглэсэн цэгүүдийн байрлалыг тодорхойлох $x, y$ тоонууд нь $x$ дэх мөр $y$ дахь багана гэснийг илтгэнэ. Мөрүүдийг дээрээс доош $1$-ээс $n$ хүртэл дугаарласан. Багануудыг зүүнээс баруун тийш $1$-ээс $m$ хүртэл дугаарласан.

Тэмдэглэсэн нүдүүд нь хэзээ ч нэг мөрөнд эсвэл нэг багананд байрлахгүй.

Гаралт

Гаралтын эхний мөрөнд замын урт $k$-г хэвлэнэ үү. Дараагийн $k$ мөр бүрт дайрч өнгөрөх нүдний координатыг дараалынх нь дагуу хэвлээрэй. (энэ зам нь ($x_1, y_1$) нүднээс эхлээд ($x_2, y_2$) нь дээр дуусах ёстой) Хэрвээ олон шийд байвал хүссэн хариугаа хэвлэж болно.

Орчуулсан: Энхсанаа

Жишээ тэстүүд

Оролт
4 4
2 2
3 3
Гаралт
15
2 2
1 2
1 1
2 1
3 1
4 1
4 2
4 3
4 4
3 4
2 4
1 4
1 3
2 3
3 3

Тэмдэглэл

The statement test is described in the picture:

Сэтгэгдлүүдийг ачааллаж байна...