B. Сурагчид болон гутлын үдээснүүд

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

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

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

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

Анна болон Мариа нар бага ангийн сурагчдын математикийн клуб-ыг хариуцахаар болжээ. Клуб-ын сурагчид бөөнөөрөө цугларах үед сурагчид маш их үймүүлдэг байв. Сурагчид маш их гутлын үдээснүүд авчирсан бөгөөд өөр хоорондоо нь үдээсээр орооцолджээ. Түүнчлэн хэрэв 2 сурагч үдээсээр уягдсан бол, уг гутлын үдээс нь эхний сурагчийг 2-дахь сурагчтай холбох бөгөөд мөн адилаар 2-дахь сурагчийг эхний сурагчтай холбож байна гэж үзнэ.

Уг үдээсний зангилааг тайлахын тулд Анна болон Мариа нар дараах зүйлсийг хийх юм. Эхлээд сурагч бүрийн хувьд Анна тухайн сурагч нь бусад ямар ямар сурагчидтай холбогдсон болохыг олж мэднэ. Хэрэв ямар нэгэн сурагч нь яг нэг ширхэг сурагчтай холбогдсон байвал, Анна тухайн сурагчид сануулга өгөх юм. Дараа нь Мариа сануулга авсан бүх сурагчдыг цуглуулан нэг бүлэг үүсгэнэ. Түүнчлэн тэрээр эдгээр бүлэг сурагчдыг клубээс хөөх юм. Уг бүлэг сурагчид нь клубээс тэр даруйдаа явах бөгөөд хөөгдсөн сурагчид нь өөрсдийг нь уяж байсан гутлын үдээсээ авч явах ажээ. Үүний дараагаар Анна дахин сурагч болгоны хувьд хэчнээн сурагчтай үдээсээр холбогдсон болохыг олж мэднэ гэх мэтчилэн үргэлжлэх юм. Ингэж дахин хэсэг бүлэг сурагчдыг клубээс хөөх замаар явсаар Анна дор хаяж нэг сурагчид сануулга өгөх хүртэл тэд үүнийг үргэлжлүүлнэ. Өөрөөр хэлбэл Анна ямар ч сурагчид сануулга өгч чадахгүй болсон үед энэ үйл явц дуусах юм.

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

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ өгөгдөх ба эдгээр нь анх байсан сурагчдын тоо болон үдээсний тоог илэрхийлнэ (). Сурагчид нь $1$-ээс $n$ хүртэл дугаарлагдсан байх бөгөөд үдээснүүд нь $1$-ээс $m$ хүртэл дугаарлагдсан байх юм. Дараагийн $m$ ширхэг мөрийн мөр болгонд 2 ширхэг бүхэл тоо $a$ болон $b$ өгөгдөх ба эдгээр нь $i$-дахь үдээсээр холбогдож буй сурагчдын дугааруудыг илэрхийлэх юм ($1 ≤ a, b ≤ n, a ≠ b$). Мөн ямар ч 2 сурагч нь нэгээс ихгүй үдээсээр холбогдсон байх бөгөөд ямар ч үдээс нь аливаа сурагчийг өөртэй нь холбоогүй байна.

Гаралт

Клубээс хөөгдөх сурагчдын бүлгийн тоог илэрхийлэх ганц бүхэл тоог хэвлэнэ үү.

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

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

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

Тэмдэглэл

Эхний жишээнд Анна болон Мариа нар нь ямар ч сурагчдын бүлгийг хөөхгүй байна. Учир нь хамгийн анхны байрлал дээр сурагч болгон нь яг 2 ширхэг бусад сурагчтайгаа холбогдсон байх бөгөөд иймд Анна ямар ч сурагчид сануулга өгч чадахгүй байх юм.

2-дахь жишээнд 4 ширхэг сурагч нь гинжин хэлбэртэй холбогдсон байх бөгөөд дахин 2 өөр сурагч нь үдээсгүй байх юм. Эхлээд Анна болон Мариа уг гинжний 2 төгсгөлд байрлах 2 ширхэг сурагчийг (1 болон 4-р сурагч) хөөх ба үүний дараагаар уг гинж дэх үлдсэн 2 сурагчийг (2 болон 3-р сурагч) хөөнө. Харин үдээсгүй байх 2 сурагч нь клубдээ үлдэх юм.

3-дахь жишээнд Анна болон Мариа нар нь агшин зуурын дотор 4-дэх сурагчаас бусад бүх сурагчдыг хөөх бөгөөд ингэснээр уг үйл явц дуусах юм. Иймд зөв хариулт нь 1 байна.

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