E. Үнэг ба олон өнцөгт

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

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

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

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

Сиел үнэг "Олон өнцөгт" гэх оньсон тоглоомыг саяхан боловсруулжээ! Энэ нь зөв $n$-ирмэгт олон өнцөгтийг гурвалжин болгон хуваах тоглох юм. Зорилго нь ямар нэг гурвалжин болгон хуваасан хуваалтыг өөр нэг уруу нь хэсэг төвөгтэй дүрмээр хувиргах юм.

$n$-ирмэгт олон өнцөгтийн гурвалжин болгох хуваалт нь аль ч 2 диагональ нь ерөнхий дотоод цэггүй байх $n - 3$ ширхэг диагоналиудын олонлог юм.

Жишээлбэл, тоглоомын анхны байрлал дээрх зургийн (a) шиг харагдах юм. Таны зорилго бол (c) шиг харагдуулах юм. Алхам бүрдээ та олон өнцөгтийн доторх нэг диагоналийг (гэхдээ олон өнцөгтийн ирмэгийн нэг биш) сонгох ба уг диагоналийг эргүүлнэ.

Та $a - b$ диагоналийг эргүүлэх гэж байгаа гэж үзье. Тэгвэл $a - b$-г тал болгон дундаа хэрэглэж байгаа 2 гурвалжин үргэлж оршино, тэдгээрийг $a - b - c$ болон $a - b - d$ гэж тэмдэглэе. Энэ үйлдлийн үр дүнд, $a - b$ нь $c - d$ диагоналиар солигдоно. Үүнээс диагоналиудын олонлог нь эргүүлэх үйлдлийн дараа мөн л олон өнцөгтийг гурвалжин болгох хуваалт байхыг хялбар баталж болно.

Иймд дээрх бодлогыг шийдэхийн тулд, та эхлээд $6 - 3$ диагоналийг эргүүлнэ, энэ нь $2 - 4$ диагоналиар солигдох юм. Дараа нь $6 - 4$ диагоналийг эргүүлэх ба үр дүнд нь (c) зураг гарах юм.

Сиел саяхан ямар ч эхлэл болон төгсгөлийн гурвалжин болгох хуваалтын хувьд уг тоглоом нь шийдэлтэй гэдгийг баталжээ. Тэрээр таныг $n ≤ 1000$-ыг хангах ямар ч оньсон тоглоомын хувьд $20 000$-аас ихгүй алхмаар уг тоглоомыг шийдэхийг хүсжээ.

Оролт

Эхний мөрөнд зөв олон өнцөгтийн ирмэгийн тоо болох бүхэл тоо $n$ ($4 ≤ n ≤ 1000$) өгөгдөнө.

Дараа нь 2 хэсэг $(n - 3)$ ширхэг мөрөөр анхны гурвалжин болгох хуваалт болон зорилгын гурвалжин болгох хуваалтыг дүрсэлнэ.

Гурвалжин болгох хуваалт бүрийн тайлбар нь $(n - 3)$ мөрөөс тогтоно. Мөр болгонд 2 бүхэл тоо $a_{i}$ болон $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$) өгөгдөх ба энэ нь $a_{i} - b_{i}$ диагоналийг дүрслэх юм.

Анхны болон зорилгын гурвалжин болгох хуваалтууд нь 2 уулаа зөв (өөрөөр хэлбэл эдгээр гурвалжин болгох хуваалтуудын ямар ч 2 диагональ ерөнхий дотоод цэггүй байна).

Гаралт

Эхлээд, алхмын тоо болох бүхэл тоо $k$ ($0 ≤ k ≤ 20, 000$)-г хэвлэнэ.

Дараа нь $k$ мөрөнд хэвлэх ба мөр болгонд 2 бүхэл тоо $a_{i}$ болон $b_{i}$ байна: эдгээр нь $i$-дахь алхмаар таны эргүүлэх диагоналийн захын цэгүүдийг илэрхийлнэ. Та $a_{i}$ болон $b_{i}$-г ямар ч дарааллаар хэвлэж болно.

Хэрэв хэд хэдэн боломжит шийдэл байгаа бол алийг нь ч хэвлэсэн болно.

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

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

Оролт
4
1 3
2 4
Гаралт
1
1 3
Оролт
6
2 6
3 6
4 6
6 2
5 2
4 2
Гаралт
2
6 3
6 4
Оролт
8
7 1
2 7
7 3
6 3
4 6
6 1
6 2
6 3
6 4
6 8
Гаралт
3
7 3
7 2
7 1

Тэмдэглэл

2-дахь жишээг дээр авч хэлэлцсэн ба зураг дээр үзүүлсэн байна.

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