Masala #5MPAQX8KKH

Xotira 2560 MB Vaqt 1000 ms

Muallif: Abduqahharov Muhammadsiddiq Elmurod o`g`li

Bog'langan shaharlar (graf)

Sizga N ta shahar va M ta yo‘l bilan tasvirlangan shaharlar tarmog‘i (graf) beriladi. Har bir yo‘l ikki shaharni bog‘laydi va yo‘llar yo‘nalishsiz. Yo‘llar o‘rtasida faqat yagona yo‘l orqali sayohat qilish talab qilinadi, ya'ni shaharlar bir-biriga uzluksiz bog‘langan bo‘lishi kerak.

Berilgan grafik bir-biriga bog‘langan komponent hosil qiladimi?
Agar yo‘q bo‘lsa, uni bir-biriga bog‘lash uchun minimal nechta yo‘l qo‘shish kerak?

Kiruvchi ma'lumotlar:

\(1 ≤ N ≤ 10^{5}\)

\(0 ≤ M ≤2*10^{5}\)

Har bir yo‘l ikki shaharni bog‘laydi: (u, v).

Chiquvchi ma'lumotlar:

Agar grafik bir-biriga to‘liq bog‘langan bo‘lsa, “YES” chiqarilsin.

Aks holda, "NO" va uni bog‘lash uchun minimal yo‘llar soni chiqarilsin.

Misollar

#	input.txt	output.txt
1	12 6 6 5 1 2 4 3 8 7 10 9 12 11	NO 5
2	5 4 1 2 2 3 3 4 4 5	YES

Izoh:

1-testda:

Har bir yo‘l ikki shaharni bog‘laydi. Yo‘llar bo‘yicha komponentlarni aniqlaymiz: 1-komponent: (6, 5) 2-komponent: (1, 2) 3-komponent: (4, 3) 4-komponent: (8, 7) 5-komponent: (10, 9) 6-komponent: (12, 11) Grafda jami 6 ta bog‘langan komponent bor.
Yangi yo‘llarni qanday qo‘shish mumkin.Masalan: (6 - 1) (2 - 3) (4 - 7) (8 - 9) (10 - 11)
Bu qo‘shimchalar bilan graf uzluksiz bo‘ladi.