ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Novosibirsk SU contest. Petrozavodsk training camp. Summer 2007

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

F. Network Attack

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
In some computer company, Mouse Inc., there is very complicated network structure. There are a lot of branches in different countries, so the only way to communicate with each other is the Internet. And it's worth to say that interaction is the key to the popularity and success of the Mouse Inc.
The CEO of this company is interested now to figure out whether there is a way to attack and devastate whole structure. Only two hackers are capable to perpetrate such an outrage — Vasya and Petya, who can destroy any two channels. If after that there are at least two servers without connection between them, then they succeed.
In other words, the company is a set of servers, some of them connected with bidirectional channels. It's guaranteed that all the servers are connected directly or indirectly. The hackers' goal is to divide network into at least two parts without any connection between them. Each hacker can destroy exactly one channel. And they can't destroy the same channel together. You are asked to count the number of ways for hackers to win.

Исходные данные

There are two integer numbers (N, M) in the first line of input: the number of servers and channels respectively (1 ≤ N ≤ 2000; 0 ≤ M ≤ 100000). In the each of the next M lines there are exactly two numbers — the indices of servers connected by channel. Channels can connect a server to itself. There can be multiple channels between one pair of servers. The servers are numbered from 1 to N.

Результат

There must be exactly one integer — the answer to the question described in the problem.

Пример

исходные данныерезультат
3 3
1 2
2 3
3 1
3
Источник задачи: Novosibirsk SU Contest. Petrozavodsk training camp, September 2007
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1557. Network Attack