Problem
Satu negeri yang bertaburan di kepulauan Oceania memutuskan untuk mencipta rangkaian jalan raya (atau lebih tepatnya, jambatan). Setiap jambatan boleh dilayari dalam kedua-dua arah. Pelan penjujukan untuk pembinaan jambatan telah dibangunkan dan diketahui bahawa selepas pembinaan semua jambatan adalah mungkin untuk memandu di atasnya dari setiap pulau ke setiap pulau (mungkin melalui beberapa pulau perantaraan
Walau bagaimanapun, detik ini mungkin datang sebelum semua jambatan dibina. Anda perlu menentukan bilangan jambatan minimum sedemikian, selepas pembinaannya (mengikut susunan yang ditentukan oleh pelan), anda boleh pergi dari mana-mana pulau ke mana-mana pulau lain.
Input
Baris pertama mengandungi dua nombor: bilangan pulau N (1≤N≤10000) dan bilangan jambatan dalam pelan M (1≤M≤50000). Kemudian terdapat garisan M, setiap satu mengandungi dua nombor x dan y (1≤x,y≤N) - nombor bandar yang disambungkan oleh jambatan seterusnya dalam pelan.
Output
Program ini harus mengeluarkan satu nombor - bilangan minimum jambatan yang dibina, selepas itu adalah mungkin untuk pergi dari mana-mana pulau ke mana-mana pulau lain.
| Input |
Output |
|
4 5
1 2
1 3
2 3
3 4
4 1
|
4 |