D. Хувиргалт

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

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

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

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

Алс хол газарт цилиндр хэлбэртэй гариг байдаг. Энэ гариг дээр доорх зурагт үзүүлсэнчлэн дээд, доод, дунд гэсэн гурван бүс нутаг байдаг.

Дээд болон доод бүс нутагт том хотууд бий. Харин дунд бүс нутаг нь далайгаас бүтсэн.

Нэг өдөр хот маш бага зайд байгаа тул дунд бүс нутгийн хэсэг газрыг эх газар болгохоор шийдсэн. Дунд бүс нутгийг нүд бүр нь дунд бүс нутгийн тэгш өнцөгт хэсгийг илэрхийлэх $r$ мөр $c$ баганатай хүснэгт хэлбэрээр дүрсэлж болно. Мөрүүд нь дээрээсээ доош 1-c $r$ хүртэл харин баганууд нь зүүнээсээ баруун тийш 1-с $c$ хүртэл дугаарлагдсан. Хэрвээ дурын хоёр нүдний аль нэг талууд нь ижил байвал уг хоёр нүдийг хөрш нүднүүд гэнэ. Нэмж хэлэхэд нэг мөрөнд хамгийн баруун болон хамгийн зүүн баганад байрласан хоёр нүд ч мөн адил хөрш нүднүүд.

Анх бүх нүд далай байсан. Төлөвлөгөө маань танд өгөгдөх тодорхой дарааллын дагуу эдгээр нүднүүдийн заримыг нь нэг нэгээр нь эх газар болгох юм.

Гэсэн хэдий ч дунд бүс нутагт байх далай нь үндсэн худалдааны зам хэлбэрээр ч мөн ашиглагддаг. Илүү тодорхой хэлбэл дараах шинж чанартай нүднүүдийн дараалал оршин байхгүй бол далайтай нүднүүдийг газар болгох боломжгүй:

  • Дарааллын бүх нүд далайтай байх (өөрөөр хэлбэл тэдгээрийг газар болгож хувиргаагүй байх).
  • Дарааллын эхний нүд нь дээд мөрөнд байх.
  • Дарааллын төгсгөлийн нүд нь доод мөрөнд байх.
  • Дарааллын дараалласан нүднүүд нь хөрш нүднүүд байх.

Иймээс төлөвлөгөөг эргэн харсан. Нүд далайгаас эх газар болж хувирах бүрт хот эхлээд үүнийг хийснээр дээрх нөхцлийг зөрчиж буй эсэхийг шалгана. Хэрвээ зөрчиж байвал уг нүд эх газар болохгүй ба төлөвлөгөө дараагийн нүдрүү шилжинэ. Бусад тохиолдолд нүд эх газар болно.

Таны ажил бол үүнийг тооцоолоод эх газар болох нүднүүдийн тоог гаргах явдал юм.

Оролт

Эхний мөрөнд гурван бүхэл тоо $r$, $c$, ба $n$ ($1 ≤ r, c ≤ 3000$, $1 ≤ n ≤ 3*10^{5}$) байна. Тэгээд дараагийн $n$ мөрөнд нүднүүдийг таны хувиргах дарааллаар тодорхойлно. Мөр бүрт $r_{i}$ ба $c_{i}$ ($1 ≤ r_{i} ≤ r$, $1 ≤ c_{i} ≤ c$) хоёр бүхэл тоо байх ба $r_{i}$ мөр болон $c_{i}$ баганад байрласан нүдийг илэрхийлнэ. Нүднүүдийг илэрхийлж байгаа бүх мөр ялгаатай байна.

Гаралт

Та эх газарруу амжилттай хувирах нүднүүдийн тоог илэрхийлэх нэг мөр хэвлэх ёстой.

Орчуулсан: Г.Мэндбаяр

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

Оролт
3 4 9
2 2
3 2
2 3
3 4
3 1
1 3
2 1
1 1
1 4
Гаралт
6

Тэмдэглэл

Доорх зургуудад жишээн дээр гүйцэтгэгдэх хувиргалтуудын дарааллыг харуулсан байна. Далай бүхий нүднүүдийг хөх өнгөөр тэмдэглэсэн бол бусад будагтай нүднүүд нь газрыг илэрхийлнэ. Хамгийн сүүлд хувирсан нүдийг бодлогын өгүүлбэр дахь нөхцөлийг зөрчсөн эсэхээс нь хамааран шар эсвэл улаан өнгөөр тэмдэглэсэн. Боломжит худалдааны замыг тасархай улаан зураасаар тэмдэглэсэн.

Зам оршин байх боломжгүй учир энэ хувиргалт хийгдэхгүй.

Зам оршин байх боломжгүй учир алгассан.

Ижил мөрөнд байгаа баруун захын болон зүүн захын нүднүүд хөрш гэдгийг сана.

Зам оршин байх боломжгүй учир алгассан.

Ингээд үр дүн:

6 амжилттай хувиргалт болон 3 амжилтгүй хувиргалт.

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