D. Orollar va ko‘priklar

Aydarko‘lda N ta orol bor, ular 1 dan N gacha raqamlangan. Orollar orasida M ta ko‘prik qurilgan; har bir ko‘prik ikki orolni bog‘laydi va undan ikki tomonga yurish mumkin.

Hokimiyat yangi ko‘priklar qurib, istalgan oroldan istalgan orolga ko‘priklar orqali o‘tish mumkin bo‘lishini xohlaydi.

1. Eng kamida nechta yangi ko‘prik qurish kerak?
2. Hozir ko‘priklar orqali bog‘langan eng katta orollar guruhida nechta orol bor?

Kirish ma’lumotlari

Birinchi qatorda N va M. Keyingi M ta qatorning har birida ikkita son u, v — ko‘prik bog‘lagan orollar. Bir juft orol orasida bir nechta ko‘prik bo‘lishi, ko‘prik orolni o‘zi bilan bog‘lashi (u = v) ham mumkin.

Chiqish ma’lumotlari

Bitta qatorda ikkita son: kerakli yangi ko‘priklar soni va eng katta guruhdagi orollar soni.

Cheklovlar

• 1 ≤ N ≤ 2 · 10⁵
• 0 ≤ M ≤ 2 · 10⁵
• 1 ≤ u, v ≤ N

1-misol: guruhlar {1, 2, 3}, {4, 5}, {6}, {7}. To‘rt guruhni zanjir qilib bog‘lash uchun 3 ta ko‘prik kerak, eng katta guruh — 3 ta orol (rasmda).

2-misol: hamma orol bog‘langan — yangi ko‘prik kerak emas.