Muallif: __thecrash__

F. Ikki rangli graf

Vaqt limiti: 1000 ms Xotira limiti: 128 mb

\(n\) ta uch va \(m\) ta qirradan iborat yo'naltirilmagan graf berilgan. Uchlar \(1\) dan \(n\) gacha raqamlangan. Grafda bir xil ikki uchni tutashtiruvchi bir nechta qirra bo'lishi mumkin, lekin uchni o'zi bilan tutashtiruvchi qirra yo'q. Graf bog'liq bo'lmasligi ham mumkin.

Grafning har bir uchini oq yoki qora rangga bo'yash kerak. Bunda har bir qirraning ikki uchi har xil rangda bo'lishi shart.

Shunday bo'yashlar ichida qora uchlar soni eng kam bo'lganini toping va shu sonni chiqaring. Agar grafni bu shartga ko'ra umuman bo'yab bo'lmasa, \(-1\) chiqaring.

Kiruvchi ma'lumotlar

Birinchi qatorda ikkita butun son \(n\) va \(m\) (\(1 \le n \le 2 \times 10^5\), \(0 \le m \le 2 \times 10^5\)) — uchlar va qirralar soni.

Keyingi \(m\) ta qatorning har birida ikkita butun son \(u\) va \(v\) (\(1 \le u, v \le n\), \(u \ne v\)) berilgan — \(u\) va \(v\) uchlarni tutashtiruvchi qirra.

Chiquvchi ma'lumotlar

Bitta son — qora uchlarning eng kam soni yoki \(-1\).

Misollar

1

7 4
1 2
1 3
1 4
5 6

2

2

3 3
1 2
2 3
3 1

-1

Izoh

Birinchi misolda 1 va 5 uchlarni qora, qolganlarini oq rangga bo'yash mumkin. Har bir qirraning uchlari har xil rangda bo'ladi, qora uchlar soni esa 2 ta. Bundan kam bo'lishi mumkin emas.

Ikkinchi misolda graf uchburchakdan iborat, uni ikki rangga to'g'ri bo'yab bo'lmaydi.