Masala D

Sizga N ta tugun va M ta qirrali (yo'naltirilmagan) graf berilgan. Tugunlar \(1\) dan \(N\) gacha raqamlangan. 

Siz grafga ba’zi yangi qirralarni qo‘shishingiz mumkin (ixtiyoriy tugunlar orasiga).

• \(K\) — grafni bog‘lash (bitta bog‘langan komponentga keltirish) uchun qo‘shiladigan minimal qirralar soni.
• \(extra_i\) — qo‘shilgan yangi qirralardan tugun i ga tutashganlari soni.
• \(max\_extra\) — \(\max \{extra_1, extra_2, \dots, extra_N\}\).

Grafni bog‘lash uchun avvalo \(K\) ning qiymati minimal bo‘lsin.
Shu minimal \(K\) bilan bog‘lash mumkin bo‘lgan yechimlar ichida esa \(max\_extra\) eng kichik bo‘lsin.

Birinchi qatorda \(N\) va \(M\) beriladi. \(1 \le N \le 100\,000,  \  0 \le M \le 100\,000\)
Keyingi \(M\) qatorda \(a\ b\) juftliklari beriladi — bu \(a\) va \(b\) tugunlar orasida qirra borligini bildiradi.
Kirishdagi qirralar takrorlanmaydi va har bir qirra uchun \(a \ne b\).

Bitta qatorda ikki son - \(K\) va \(max_{extra}\) ni chiqaring.