B. Баавгай ба шадар гурван цэрэг

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

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

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

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

Шадар гурван цэргийн тухай домгийг мэдэх үү? Хэрэв мэдэхгүй бол энэ бодлогоос мэдэж аваарай.

Ричэлимаки бол Биарис хотын жанжин. Тэрээр гэмт хэрэгтэй өөрийн биеэр тэмцсээр залхжээ. Түүнд муу залуустай тэмцэх эрэлхэг гурван дайчин хэрэг болов.

$n$ дайчин байв. Ричэлимаки тэднээс шадар гурван цэрэг сонгоно. Гэхдээ тийм ч амархан сонгохгүй. Хамгийн чухал нөхцөл бол шадар гурван цэрэг хамтран ажиллахын тулд нэгнийгээ мэддэг байх шаардлагатай. Мөн тэд олон танилтай байвал урвах үзэгдэл гарч болзошгүй тул олон танилтай байж болохгүй. Шадар цэргийн танилын тоо гэдгээр бусад хоёр шадар цэргээс ялгаатай түүний танил цэргийн тоог ойлгоно.

Ричэлимакид нэгнийгээ таньдаг гурван цэрэг сонгож болох эсэхийг мэдэн, тэдний танилын тооны нийлбэрийг хамгийн багадаа хэд байж болохыг олж өгнө үү.

Оролт

Эхний мөрөнд дайчдын тоо болон нэгнийгээ таних хамаарлын тоог илэрхийлэх $n$ ба $m$ ($3 ≤ n ≤ 4000$, $0 ≤ m ≤ 4000$) гэсэн тоонууд өгөгдөнө.

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

Гаралт

Хэрэв Ричэлимаки шадар гурван цэрэг сонгож чадах бол тэдний танилын тоонуудын нийлбэр хамгийн багадаа хэд байж болохыг хэвлэ. Бусад тохиолдолд "-1" гэж хэвлэ.

Орчуулсан: Бат-Од

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

Оролт
5 6
1 2
1 3
2 3
2 4
3 4
4 5
Гаралт
2
Оролт
7 4
2 1
3 6
5 1
1 7
Гаралт
-1

Тэмдэглэл

Эхний жишээнд Ричэлимаки $1$, $2$, $3$ гэсэн гурвалыг сонгох хэрэгтэй. Эхний шадар цэргийн танил $0$. Хоёр дахь шадар цэрэг $4$ дугаарын дайчинг таних тул түүний танил $1$ байна. Гурав дахь шадар цэрэг мөн $4$ дугаарын дайчинг таних тулд түүний танил $1$ байна. Тиймээс нийт танил $0 + 1 + 1 = 2$ байна.

Өөр нэгэн боломжит гурвал нь $2, 3, 4$ боловч тэдний танилын нийлбэр $1 + 1 + 1 = 3$.

Хоёр дахь жишээнд нэгнийгээ таних гурвал байгүй.

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