E. Шинэчлэлт

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

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

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

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

Берландад $m$ хос чиглэлтэй замаар холбогдсон $n$ хот бий. Ямар ч зам хотыг өөртэй нь холбохгүй ба ямар ч хос хотууд хоорондоо нэгээс их замаар холбогдохгүй. Та дурын хотоос өөр дурын хотруу зөвхөн оршин байгаа замуудыг ашиглан очиж чаддаг байх албагүй.

Берландын ерөнхийлөгч замын системд шинэчлэлт хийхээр шийдсэн ба Тээврийн яаманд энэ шинэчлэлтийг хийх заавар өгсөн. Одоо зам бүр нэг чиглэлтэй (зөвхөн нэг хотоос нөгөөрүү чиглэнэ) байх ёстой.

Оршин суугчид дундаас их дургүйцэл гаргахгүйн тулд шинэчлэлт боломжит хамгийн бага салангид хоттой байхаар хийгдэх хэрэгтэй. Салангид хот гэдэг нь ямар ч зам энэ хотруу хөтлөөгүй ч энэ хотоос бусад зам эхэлж болох хотыг хэлнэ.

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

Оролт

Оролтын эхний мөрөнд хоёр эерэг бүхэл тоон утга $n$ ба $m$ байх ба Берланд дахь хотууд болон замуудын тоо байна ($2 ≤ n ≤ 100 000$, $1 ≤ m ≤ 100 000$).

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

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

Гаралт

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

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

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

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

Тэмдэглэл

Эхний жишээн дээр дараах замын чиглэлүүд зөвшөөрөгдөнө: , , .

Хоёр дахь жишээн дээр: , , , , .

Гурав дахь жишээн дээр: , , , , .

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