E. Тэмцээн

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

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

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

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

Квадрат матрицын 2-дахь диагональ гэдэг нь баруун дээд булангаас зүүн доод булан хүртэлх диагоналийг нэрлэдэг ажээ. $n$ төвшний шатны гишгүүр гэдгээр 2-дахь диагональ-аас дээш ямар ч нүд агуулаагүй байх $n × n$ хэмжээ бүхий квадрат матрицыг тодорхойлъё (доорх зурагт 5 төвшний шатны гишгүүрийг дүрслэв).

$n$ төвшний шатны гишгүүрийн нүднүүд дээр $m$ ширхэг тамирчин байв.

Тамирчин нь шатны гишгүүрийн талаараа зэргэлдээх нүд уруу нүүх дээ 1 секунд зарцуулдаг ажээ. Тэмцээн эхлэхээс өмнө тамирчин болгон нь 2-дахь диагональд хүрч очих хамгийн богино замуудаас нэгийг сонгох ёстой байв.

Шүгэл дуугарсны дараа тэмцээн эхлэх бөгөөд бүх тамирчид нь өөрсдийн сонгогдсон замын дагуу хөдлөх юм. Ямар нэгэн тамирчин 2-дахь диагоналийн ямар нэгэн нүдэнд очмогцоо зогсох бөгөөд дахин хөдлөхөө болих ажээ. Түүнчлэн бүх тамирчид 2-дахь диагональд хүрмэгц тэмцээн өндөрлөх ёстой байв. Хэрэв тэмцээний туршид ямар ч 2 тамирчин нь нэгэн зэрэг ижил нүдэнд оршин байгаагүй бол уг тэмцээнийг амжилттай болсон гэж үзэх юм. Мөн 2-дахь диагоналийн ямар ч нүд нь 1-ээс олон тооны тамирчин агуулсан байж болохгүй. Хэрэв аливаа тамирчин өгөгдсөн хугацааны мөчид нэгэн нүдийг орхин явах бөгөөд өөр нэгэн тамирчин уг нүдэнд ирж байвал эдгээр тамирчдыг нэгэн зэрэг ижил нүдэнд оршин байна гэж үзэхгүй. Сонгогдсон замууд нь хамгийн богино учраас өөр ямар нэгэн онцгой тохиолдлууд (жишээлбэл 2 тамирчин нэг нэгнийхээ өөдөөс хөдлөх) гарах боломжгүй байхыг анхаарна уу.

Танд шатны гишгүүр дээр байрлаж буй $m$ ширхэг тамирчдын байрлал өгөгдөв. Таны даалгавар бол уралдаан нь амжилттай болж өндөрлөхөөр өөрөөр хэлбэл тамирчдын хувьд аль ч 2 тамирчин нь нэгэн зэрэг ижил нүдэнд оршоогүй байхаар хамгийн богино замуудыг сонгож болдог байхаар эдгээр өгөгдсөн тамирчдын дундаас боломжит хамгийн олон тооны тамирчдыг сонгох явдал юм. Сонгогдоогүй үлдсэн бусад бүх тамирчид нь тэмцээн эхлэхээс өмнө шатны гишгүүрээс холдсон байна.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ ($1 ≤ n, m ≤ 10^{5}$) өгөгдөнө. Дараа нь $m$ ширхэг мөрөнд шатны гишгүүр дээрх тамирчдын координатууд нь хос бүхэл тоо $r_{i}, c_{i}$ ($1 ≤ r_{i}, c_{i} ≤ n$, $n - c_{i} < r_{i}$) хэлбэртэйгээр өгөгдөх ба энд $r_{i}$ нь шатны гишгүүрийн мөрийн дугаарыг $c_{i}$ нь баганын дугаарыг илэрхийлнэ (мөр болон баганын дугаарлалтыг ойлгохын тулд бодлогын өгүүлбэрт өгөгдсөн жишээ зургийг харна уу). Мөн ямар ч 2 тамирчин шатны гишгүүрийн ижил нүдэнд байрлаагүй байна.

Гаралт

Эхний мөрөнд сонгогдсон тамирчдын тоог хэвлэнэ үү. 2-дахь мөрөнд сонгогдсон тамирчдын дугааруудыг дурын дарааллаар хэвлэх бөгөөд хооронд нь зайгаар тусгаарлан хэвлэнэ үү. Хэрэв хэд хэдэн боломжит хариултууд байвал та тэдгээрийн алийг нь ч хэвлэсэн болно. Тамирчид нь оролтод өгөгдсөн дарааллынхаа дагуу 1-ээс эхлэн дугаарлагдсан байна.

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

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

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

Тэмдэглэл

Эхний жишээний тайлбар доор өгөгдөв.

Зурагт 3 төвшний шатны гишгүүрийг дүрслэв. Уг зурагт байрлах сумнууд нь сонгогдсон тамирчдын хамгийн богино замуудыг илэрхийлэх юм.

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