Странная сеть
(Время: 1 сек. Память: 32 Мб Сложность: 65%)
В одной из самых крупных IT-компаний уже много лет действует локальная сеть, в которую входят N компьютеров, последовательно пронумерованных целыми числами от 1 до N. Для соединения компьютеров используется провод специального типа. С помощью одного провода можно напрямую соединить ровно два компьютера, причем соединение позволяет передавать данные в двух направлениях. Каждый компьютер имеет два порта, поэтому он может быть соединен напрямую не более чем с двумя другими компьютерами. Сеть организована таким образом, что если два компьютера не соединены напрямую проводом, то передача данных может осуществляться через промежуточные компьютеры. Путем передачи данных между компьютерами с номерами V1 и VK называется такая последовательность компьютеров V1, V2, … , VK-1, VK, что для любого 2 ≤ i ≤ K существует прямое соединение между компьютерами Vi-1 и Vi. Длиной пути передачи данных считается количество используемых промежуточных компьютеров. Минимальным путем передачи данных между компьютерами Vi и Vj является такой путь передачи данных, длина которого минимальна из возможных.
Для приведенного ниже примера длина минимального пути передачи данных между компьютерами 1 и 8 равна 2, а между компьютерами 2 и 7 равна 1, между компьютерами 2 и 4 равна 0.
Если не существует ни одного пути передачи данных между какими-либо двумя компьютерами, то в данном случае длина минимального пути передачи данных между этими компьютерами считается равной нулю. Для приведенного выше примера между компьютерами 1 и 4 не существует пути передачи данных, поэтому длина минимального пути передачи данных равна 0.
Для выяснения эффективности локальной сети необходимо определить коэффициент связности, значение которого равно сумме длин минимальных путей передачи данных между всеми парами компьютеров. Пары, отличающиеся порядком следования элементов считаются различными, то есть пара (1, 2) и (2, 1) считаются различными.
Вашей задачей является определить значение коэффициента связности для заданной локальной сети.
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа N и M – число компьютеров и число прямых соединений соответственно (2 ≤ N ≤ 105, 1 ≤ M ≤ 106). Числа разделены одиночным пробелом.
Каждая из следующих M строк содержит описание одного прямого соединения. Каждое прямое соединение описывается при помощи двух целых чисел Xi и Yi (1 ≤ Xi, Yi ≤ N; Xi ≠ Yi), разделенных пробелом – номера соответствующих компьютеров, соединенных напрямую. Известно, что Xi ≠ Xj или Yi ≠ Yj, если i ≠ j. Строки в файле нумеруются последовательно, начиная с единицы.
Выходные данные
Единственная строка выходного файла OUTPUT.TXT должна содержать одно целое число – коэффициент связности локальной сети.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2 1
1 2 | 0 |
| 2 | 4 4
1 2
2 3
4 3
1 4 | 4 |
| 3 | 8 7
1 3
3 6
4 2
7 4
2 5
5 7
6 8 | 12 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
