F. Үст хорхой

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

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

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

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

Хэрэв ямар нэгэн чиглэлгүй граф нь тухайн графын $p$ замаас бусад дурын оройнууд хүртэлх зай нь хамгийн ихдээ 1 байдаг $p$ зам агуулах бөгөөд цикл агуулаагүй, холбоост байвал тус графыг бид үст хорхой хэмээн нэрлэдэг. Үст хорхой нь гогцоо (ямар нэгэн оройноос уг орой хүрэх ирмэг) агуулж болох боловч олон тооны (параллель) ирмэгүүд агуулсан байж болохгүй.

Дараах зурагт үст хорхойн нэгэн жишээг дүрслэв:

Танд чиглэлгүй $G$ граф өгөгдөнө. Та нэгтгэх үйлдэл хийж болох ба эдгээр нэгтгэх үйлдлийг хийх болгондоо 2 оройг нэг орой болгон нэгтгэх юм. Ямар нэгэн сонгогдсон $a$ болон $b$ ($a ≠ b$) оройнуудыг авч үзье. Нэгтгэх үйлдлийг уг оройнууд дээр хийхэд эдгээр оройнууд нь өөрсдийн ирмэгүүдийн ($a$ эсвэл $b$ оройнуудын дор хаяж нэгтэй нь холбогдсон ирмэгүүд) хамт устах боловч шинэ $w$ орой болон ($a, w$) эсвэл ($b, w$) ирмэг бүрийн хувьд тодорхойлогдох $(x, w)$ ирмэгүүд уг граф-д нэмэгдэх юм. Хэрэв $(a, b)$ гэсэн ирмэг байсан бол уг ирмэг нь $(w, w)$ гэсэн гогцоо болж хувирна. Үр дүнгийн граф (нэгтгэх үйлдлийн дараах граф) нь хос оройнуудын хооронд олон тооны (параллель) ирмэгүүд агуулсан байж болох бөгөөд мөн гогцоонууд агуулсан байж болно. Түүнчлэн уг үйлдэл нь графын оройнуудын тоог 1-ээр багасгах боловч графын ирмэгийн тоо хэвээр үлдэж байгааг анхаарна уу.

Нэгтгэх үйлдлийг энгийнээр тайлбарлавал графын 2 оройг нэгтгэн энгийн хувирлаар үүссэн ирмэгүүд бүхий нэг орой үүсгэх үйлдэл юм.

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

Оролт

Эхний мөрөнд хос бүхэл тоонууд $n$, $m$ ($1 ≤ n ≤ 2000;0 ≤ m ≤ 10^{5}$) өгөгдөх ба энд $n$ нь графын оройн тоог, $m$ нь уг граф дахь ирмэгийн тоог илэрхийлнэ. Дараагийн $m$ ширхэг мөрөнд ирмэгүүдийн тайлбар өгөгдөх ба мөр болгонд нэг ирмэгийн тайлбар өгөгдөнө. Мөр болгонд хос бүхэл тоо $a_{i}, b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n;a_{i} ≠ b_{i}$) өгөгдөх бөгөөд $a_{i}, b_{i}$ нь уг ирмэгээр холбогдсон оройнуудын дугааруудыг илэрхийлэх юм. Мөн оройнууд нь 1-ээс $n$ хүртэл дугаарлагдсан байна. Өгөгдсөн графын дурын хос оройны хооронд нэгээс ихгүй ирмэг байх бөгөөд өгөгдсөн граф нь заавал холбоост граф байх шаардлагагүй.

Гаралт

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

Орчуулсан: Баатархүү

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

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