Қосылу индексі
Ғаламторлэндте \(n\) қала бар және кейбір қалалар жұптарының арасында екі жаққа бағытталған жолдар бар. Олар кез-келген қаладан кез-келген басқа қалаға жетуге болатындай қосылған. Барлық қалалар \(1,\ldots,n\) сандарымен нөмірленген. Сонымен қатар \(2\) астана бар: мәдени астана \(1\) және ресми астана \(n\).
ITар (Айтиар) елдегі жолдармен айналысады және жағдайды жақсартайын деп шешті. Ол үшін ол \(A\) және \(B\) қалаларының арасындағы қосылу индексін белгіледі. Бұл индекс осылай саналады: әр тікелей жолмен қосылмаған қалалар жұбы \(C\) және \(D\) үшін, \(CD\) жолы қосылған кезде \(A\) және \(B\) қалаларының арасындағы ең қысқа жолдың ұзындығы саналады; барлық саналған ұзындықтарды қосу арқылы қосылу индексі есептелінеді.
\(A\) және \(B\) қалаларының арасындағы ең қысқа жол – \(P_0 = A, P_1, \ldots, P_k = B\) және барлық \(i=0,\ldots,k-1\) үшін \(P_i\) және \(P_{i+1}\) арасында жол бар қалалар тізбегі табылатындай ең кем жолдар саны \(k\).
ITар үкіметке астаналар арасында (жақсы) жол салыну керек екенін көрсеткісі келеді. Ол үшін оған сіздің көмегіңіз керек. ITарға екі астана арасында қосылу индексін санауға көмектесіңіз.
Input
Бірінші жолда екі бүтін сан \(n\) және \(m\) (\(1\le n, m \le 2 \cdot 10^5)\) — қалалар және жолдар саны берілген.
Келесі \(m\) жолда екі бүтін сан \(u\) және \(v\) (\(1\le u, v \le n, u \neq v\)) — елдегі жолдардың сипаттамасы берілген.
Кез-келген қаладан кез-келген басқа қалаға жетуге болатындығына кепілдік беріледі. Сонымен қатар, әр қалалар жұбының арасында ең көп дегенде бір жол бар екеніне кепілдік беріледі және әрбір жол екі әртүрлі қалаларды қосады.
Output
Бір бүтін сан шығарыңыз – астаналар арасындағы қосылу индексі.
Sample Input 1
3 2
1 2
2 3Sample Output 1
1Sample Input 2
8 10
1 4
4 3
3 6
6 2
2 8
8 5
5 7
6 7
2 5
3 7Sample Output 2
60
Пікірлер
Был сделан rejudge. Все посылки протестированы.
Задача под следствием. Все посылки будут протестированы после обновления.