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
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.
Источник задачи: Novosibirsk SU Contest. Petrozavodsk training camp, September 2007