Masala #0128

Xotira 16 MB Vaqt 1000 ms
14

Yo’l qurilishi

Baytobodda 1 dan n gacha raqamlangan n ta mahalla va ularni bog’lovchi m ta yo’l bor. Har bir yo’l ikkita mahallani bir biriga bog’laydi.

Shaharda harakatlanish oson bo’lishi uchun hukumat Baytobodga yangi yo’llarni qurmoqchi, bunda Baytoboddagi a, b va c mahallalarni oladigan bo’lsak, a mahalladan b mahallaga va a mahalladan c mahallaga yo’l bo’ladigan bo’lsa, b va c mahallalarni bog’lovchi yangi yo’l quriladi. Agar bu yo’l avvaldan mavjud bo’lsa, yangi yo’l qurilmaydi.

Shu yo’sinda qancha yo’l qurish mumkinligini toping.


Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita n va m sonlari beriladi, bu sonlar mos ravishda mahallalar soni va ularni bog’laydigan yo’llar sonini bildiradi (1 ≤ n, m ≤ 105).

Keyingi m ta qatorda esa, yo’llarni tavsiflovchi ikkita u va v sonlari beriladi, bu esa u va v raqamli shaharlar orasida ikki tomonli yo’l borligini bildiradi(1 ≤ u, v ≤ 105, u ≠ v). Ixtiyoriy ikkita shahar orasida ko’p bilan bitta yo’l bo’lishi mumkin.


Chiquvchi ma'lumotlar:

Bitta son – yangi quriladigan yo’llar sonini chop eting.


Misollar
# input.txt output.txt
1
6 3
1 2
2 3
4 5	
1
Izoh:

Berilgan misolda faqat 1-va 3- mahallalarni bog’lovchi yo’l qurish mumkin