ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Novosibirsk SU contest. Petrozavodsk training camp. Summer 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Network Attack

Time limit: 2.0 second
Memory limit: 64 MB
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.

Input

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.

Output

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

Sample

inputoutput
3 3
1 2
2 3
3 1
3
Problem Source: Novosibirsk SU Contest. Petrozavodsk training camp, September 2007
To submit the solution for this problem go to the Problem set: 1557. Network Attack