Problem
Okyanusya adalarına dağılmış bir eyalet, bir yol ağı (veya daha doğrusu köprüler) oluşturmaya karar verdi. Her köprüde her iki yönde de gezinilebilir. Köprülerin inşası için bir sıralama planı geliştirilmiştir ve tüm köprülerin inşasından sonra her bir adadan (belki bazı ara adalardan) köprülerin üzerinden geçmenin mümkün olacağı bilinmektedir.
Ancak bu an, tüm köprüler inşa edilmeden önce gelebilir. İnşaatından sonra (planda belirlenen sırayla) herhangi bir adadan diğerine gitmek mümkün olacak asgari köprü sayısını belirlemeniz gerekir.
Giriş
İlk satır iki sayı içerir: adaların sayısı N (1≤N≤10000) ve M planındaki köprülerin sayısı (1≤M≤50000). Ardından, her biri iki sayı x ve y (1≤x,y≤N) içeren M çizgiler vardır - planda bir sonraki köprüyle birbirine bağlanan şehirlerin numaraları.
Çıktı
Programın çıktısı tek bir sayı olmalıdır - inşa edilen minimum köprü sayısı, bundan sonra herhangi bir adadan diğerine gitmek mümkün olacaktır.
| Giriş |
Çıktı |
|
4 5
1 2
1 3
2 3
3 4
4 1
|
4 |