D. Өнгөтэй граф

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

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

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

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

Танд $n$ орой $m$ ирмэгтэй чиглэлгүй граф өгөгдсөн. Бид графийн оройнуудыг $1$-с $n$ хүртэл дугаарлаж авч үзнэ. Графын орой бүр өнгөтэй. $i$-р оройн өнгө нь $c_{i}$ бүхэл тоон утга юм.

Графын бүх оройг ижил $k$ өнгөөр будагдсан гэж үзье. $V(k)$ шиг бүрдлийг тэмдэглэе. $k$ өнгөөс ялгаатай хөршийн өнгийн утгыг $Q(k) = {c_{u} :  c_{u} ≠ k$ бүрдлийн элементүүд хэлбэрээр тэмдэглэе мөн графын ирмэгээр холбогдсон $v$ болон $u$ оройнууд шиг $V(k)$ бүрдэлд хамаарах $v$ орой байгаа.

Таны ажил бол $Q(k)$ бүрдлийн элементийн тоог хамгийн их байлгах $k$ шиг өнгийг олох. Өөрөөр хэлбэл та хамгийн олон ялгаатай хөрштэй өнгийг олохыг хүсч байна. Та $k$ шиг өнгө олохыг хүсч байгаа бөгөөд энэ нь графд тухайн өнгөтэй ядаж нэг орой байх ёстой.

Оролт

Оролтын эхний мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоон утга $n, m$ $(1 ≤ n, m ≤ 10^{5})$ байх ба харгалзан орой болон ирмэгийн тоо юм. Хоёр дахь мөрөнд бүхэл тоон дараалал $\c_{1}, c_{2}, ..., c_{n}$ $(1 ≤ c_{i} ≤ 10^{5})$ байх ба графын оройнуудын өнгө. Уг мөрөнд байгаа тоонууд зайгаар тусгаарлагдана.

Дараагийн $m$ мөрөнд ирмэгүүдийн тодорхойлолт байна: $i$-р мөр зайгаар тусгаарлагдсан хоёр бүхэл тоон утга $a_{i}, b_{i}$ $(1 ≤ a_{i}, b_{i} ≤ n; a_{i} ≠ b_{i})$ байх ба $i$-р ирмэгээр холбогдсон оройнуудын дугаар юм.

Өгөгдсөн граф нь орой уруу давтсан болон давхар ирмэг байхгүй.

Гаралт

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

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

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

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