B. Аюулгүй нүднүүд

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

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

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

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

Васяд $m$ тэрэг ба $n × n$ хэмжээтэй квадрат шатрын хөлөг байна. Анх шатрын хөлөг хоосон байна. Вася тэргүүдийг нэг нэгээр нь хөлөг дээр тавина.

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

Танд Васягийн хөлөг дээр тэрэгнүүдийг тавих байрлалууд өгөгдөнө. Та тэрэг бүрийн хувьд Вася тэргийг хөлөг дээр тавьсаны дараа аюулгүй (тэрэгний хөлд байхгүй) байх нүднүүдийн тоог тодорхойлох ёстой.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоо $n$ ба $m$ ($1 ≤ n ≤ 100 000$, $1 ≤ m ≤ min(100 000, n^{2})$) байх буюу хөлгийн хэмжээ болон тэргүүдийн тоо байна.

Дараагийн $m$ мөр бүрт бүхэл тоон утгууд $x_{i}$ ба $y_{i}$ ($1 ≤ x_{i}, y_{i} ≤ n$) байх ба Васягийн $i$-р тэргийг тавих мөр болон баганын дугаар юм. Вася тэргүүдийг оролтонд өгсөн дарааллаар хөлөг дээр тавина. Мэдээж ямар ч нүдэнд нэгээс олон тэрэг байрлахгүй.

Гаралт

$m$ бүхэл тоон утгыг хэвлэх ба эдгээрийн $i$-р тоо нь эхний $i$ тэргийг тавьсаны дараах аюулгүй (тэрэгний хөлд байхгүй) нүднүүдийн тоо байх ёстой.

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

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

Оролт
3 3
1 1
3 1
2 2
Гаралт
4 2 0 
Оролт
5 2
1 5
5 1
Гаралт
16 9 
Оролт
100000 1
300 400
Гаралт
9999800001 

Тэмдэглэл

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

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