B. Баг хуваарилах

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

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

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

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

Нэгэн өдөр $n$ тооны хүүхэд стадионд ирээд хөлбөмбөг тоглохоор болжээ. Мэдээж тоглохын тулд тэд $2$ багт хуваагдах ёстой бөгөөд багууд тэнцүү тооны хүнтэй байх хэрэгтэй.

Бидэнд мэдэгдснээр хүүхдүүд таардаггүй хүнтэй ажээ. Нэг хүн хамгийн ихдээ $2$ хүнтэй таардаггүй. Мөн $A$ хүн $B$-тэй таардаггүй бол $B$ хүн $A$-тай таардаггүй.

Хоорондоо таардаггүй хүмүүсийг нэг багт оруулж болохгүй. Дээрх шаардлагын дагуу баг хуваах боломжгүй бол зарим хүүхдүүдийг сэлгээнд суулгах хэрэгтэй.

Хамгийн цөөн хүүхдийг сэлгээнд суулгаж, дээрх өгөгдсөн шаардлагыг хангах баг хуваагаад тоглолтоо эхэлцгээе!

Оролт

Эхний мөрөнд хүүхдүүдийн тоо $n$ болон таардаггүй харьцааны тоо $m$ ($2 ≤ n ≤ 100$, $1 ≤ m ≤ 100$) өгөгдөнө.

Дараагийн $m$ мөр бүрт таардаггүй харьцааг илэрхийлэх $a_i$, $b_i$ ($1 ≤ a_i, b_i ≤ n$, $a_i ≠ b_i$) өгөгдөнө. Энэ нь хүүхдүүдийн дугаар юм. Нэг таардаггүй харьцаа яг нэг удаа л оролтонд байна. Энд нэг хүүхэд хоёроос илүү таардаггүй хүнтэй байхгүй.

Гаралт

Сэлгээнд суулгах шаардалгатай хамгийн цөөхөн хүүхдийн тоо болох ганц бүхэл тоог хэвлэ.

Орчуулсан: zoloogg

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

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