F. Хоёр хэсэгтэй графын ирмэгүүдийг будах

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

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

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

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

Танд давхар ирмэггүй чиглэлгүй хоёр хэсэгтэй граф өгөгдсөн. Та графын ирмэгүүдийг хамгийн цөөн тооны өнгөөр будах ёстой ба хөрш хоёр ирмэг ижил өнгөтэй байж болохгүй.

Оролт

Эхний мөрөнд гурван бүхэл тоон утга $a, b, m$ ($1 ≤ a, b ≤ 1000$, $0 ≤ m ≤ 10^{5}$) байх ба $a$ нь эхний хэсгийн хэмжээ бол $b$ нь хоёр дахь хэсгийн хэмжээ бол $m$ нь графын ирмэгүүдийн тоо.

Дараагийн $m$ мөр бүрт хоёр бүхэл тоон утга $x, y$ ($1 ≤ x ≤ a, 1 ≤ y ≤ b$) байх ба $x$ нь эхний хэсэгт байгаа оройн дугаар бол $y$ нь хоёр дахь хэсэгт байгаа оройн дугаар. Давхар ирмэг байхгүй.

Гаралт

Эхний мөрөнд өнгөнүүдийн хамгийн бага тоог илэрхийлэх $c$ бүхэл тоон утгыг хэвлэ. Хоёр дахь мөрөнд $1$-c $n$-н хооронд орших $m$ бүхэл тоон утгыг хэвлэх буюу ирмэгүүдийн өнгө (оролтонд өгсөн дарааллаар хэвлэнэ).

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

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

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

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