Unfair Competition

Limits: 2 sec., 256 MiB

In the final round of “Miss High School” there are only two girls — Marichka and her foe Khrystya. Tomorrow each of high school students will vote for one of them.

Every student in the high school adores Marichka and prefers voting for her. However Khrystya has bribed one of the students Petryk thus he will vote for her tomorrow. Moreover he will convince all his friends to vote for Khrystya and they will convince their friends and then friends of the friends of the friends and so on.

Zenyk is aware of this evil plan. Also he knows that Marichka will lose only if all studends from Petryk’s network of friends vote against her. Thus if he manages to change at least one vote in favour of Marichka she will be “Miss High School”.

There are N students in Petryk’s network of friends numbered from 1 to N (Petryk has number 1). Also there are M friendship connections in this network, i.e. M pairs of friends. It is known that the network is connected.

Zenyk can break only one friendship relation as he doesn’t have much time. Your task is to count the number of ways Zenyk can make Marichka the miss, i.e. the number of ways to break one friendship relation that will change at least one vote in favour of Marichka.

Input

The first line contains two integers N and M separated by a single space. Each of the following M lines contains a pair of integers \(\mathbf{a_i}, \mathbf{b_i}\) separeted by a single space. Here students \(\mathbf{a_i}\) and \(\mathbf{b_i}\) are connected by the i-th friendship relation.

Output

The nubmer of ways to break one friendship relation which will make Marihka the miss.

Constraints

\(1 \le \mathbf{N} \le 500\),

\(1 \le \mathbf{M} \le 5000\),

\(1 \le \mathbf{a_i}, \mathbf{b_i} \le N\),

\(\mathbf{a_i} \neq \mathbf{b_i}\).

Samples