D. Аялал

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

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

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

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

Берландын газар нутаг нь $n × m$ хэмжээ бүхий тэгш өнцөгтөн талбайгаар дүрслэгддэг. Берландын эзэн хаан нь нийслэл хотдоо амьдрах бөгөөд нийслэл хот нь зүүн дээд талын $(1, 1)$ гэсэн нүдэнд байрладаг байв. Баруун доод талын нүд нь $(n, m)$ гэсэн координатуудтай байх юм. Нэгэн өдөр эзэн хаан бусад бүх нүднүүдээр (нийслэл хотыг тооцохгүй) яг нэг удаа дайрч өнгөрөн, өөрийн бүх нутаг дэвсгэрээрээ аялан явсаар эргэн нийслэл хотдоо ирэх аялалд гарахаар шийджээ. Ингэснээр эзэн хаан нийслэл хотыг яг 2 удаа дайрах бөгөөд уг аяллын эхэнд болон яг төгсгөлд л дайрах юм. Эзэн хаан зөвхөн хөрш талтай нүднүүд уруу нүүж чадна. Тэгсэн хэдий ч хааны зөвлөгч эзэн хаан уг аяллыг хийж чадахгүй байх боломжтой хэмээн хэлжээ. Гэхдээ нэгэн арга байгаа бөгөөд тухайлбал хэн нэгэн зарим нүднүүдийн хооронд нэг талын шилжигч систем зохион бүтээсэн ба ингэснээр эзэн хаан өөрийн аяллаа гүйцэлдүүлж чадах юм. Нэг нүдэнд нэгээс илүү тооны шилжигч систем байрлуулсан байж болохгүй бөгөөд шилжигч систем бүрийг хэдэн ч удаа хэрэглэж болох юм. Гэхдээ ямар ч шилжигч системтэй нүдний хувьд шилжигч системийг хэрэглэх болгонд яг л ижилхэн нүд уруу шилжүүлэх юм. Өөрөөр хэлбэл хэдэн ч удаа шилжигч системийг хэрэглэсэн нэг л нүд уруу шилжинэ гэсэн үг юм. Эзэн хаан шилжигч систем байрлуулсан нүдэнд очмогцоо уг шилжигч системийг хэрэглэх эсэхээ өөрөө шийддэг. Тэгвэл эзэн хаан уг аяллаа гүйцэлдүүлэхийн тулд хамгийн багадаа хэчнээн тооны шилжигч систем байрлуулах ёстой вэ? Мөн та эзэн хаанд уг аяллын маршрутыг гаргаж өгнө үү.

Оролт

Эхний мөрөнд талбайн хэмжээг илэрхийлэх зайгаар тусгаарлагдсан 2 бүхэл тоо $n$ болон $m$ ($1 ≤ n, m ≤ 100, 2 ≤ $ $n$ $*$ $m$) өгөгдөнө. Зүүн дээд нүд нь $(1, 1)$, баруун доод нүд нь $(n, m)$ гэсэн координатуудтай байна.

Гаралт

Эхний мөрөнд хамгийн бага шилжигч системийн тоо болох бүхэл тоо $k$-г хэвлэнэ. Дараа нь $k$ ширхэг мөрөнд мөр болгонд 4 ширхэг бүхэл тоо $x_{1}$ $y_{1}$ $x_{2}$ $y_{2}$ ($1 ≤ x_{1}, x_{2} ≤ n, 1 ≤ y_{1}, y_{2} ≤ m$) байхаар хэвлэх бөгөөд эдгээр нь шилжигч системийг байрлуулах нүдний координатууд ($x_{1}, y_{1}$) болон уг шилжигч системийг ашиглан шилжин очих нүдний координатууд ($x_{2}, y_{2}$)-ыг илэрхийлнэ.

Дараа нь $nm + 1$ мөрөнд мөр болгонд 2 тоо байхаар хэвлэх бөгөөд эдгээр тоонууд нь эзэн хааны дайрч өнгөрсөн дарааллын дагуу нүднүүдийн координатуудыг илэрхийлэх юм. Уг аялал нь $(1, 1)$ гэсэн нүднээс эхлэн уг нүдэнд дууссан байх ёстой. Эзэн хаан хөрш талтай нүднүүд уруу болон шилжигч систем ашиглан шилжин очиж болох нүднүүд уруу нүүж чадах юм. Түүнчлэн тэрээр нийслэл хотоор яг 2 удаа дайрсан байх бөгөөд бусад нүднүүдээр яг нэг удаа дайрсан байх ёстой юм.

Орчуулсан: Баатархүү

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

Оролт
2 2
Гаралт
0
1 1
1 2
2 2
2 1
1 1
Оролт
3 3
Гаралт
1
3 3 1 1
1 1
1 2
1 3
2 3
2 2
2 1
3 1
3 2
3 3
1 1
Сэтгэгдлүүдийг ачааллаж байна...