Portal Construction

King Byteasar rules a solar system with (N) planets numbered from 1 to (N). His palace is on planet 1 and his military base on planet 2. A long time ago, the king established a teleportation portal between these two planets, which takes (250) minutes for travel. Modern teleportation devices, however, allow travel between any two directly connected planets in just (60) minutes. Some pairs of planets are already connected with these new portals, and it is possible to travel between planets 1 and 2 using them, but the journey takes at least 5 portals (i.e. at least (5 \times 60 = 300) minutes), so as not to be faster than the king’s private portal.

Now, every pair of planets that are not directly connected is petitioning for a new portal. Being both economical and security–conscious, the king wants to approve as many new portal constructions as possible, provided that after adding any single new portal (to the existing network) the time needed to travel from planet 1 to planet 2 using new portals is not less than 250 minutes (i.e. the number of portals in any path between them is at least 5).

Formally, you are given a graph with (N) nodes and (M) existing bidirectional edges (portals). For any candidate edge ((u, v)) (with (u < v)) which is not already present in the graph, let (d_1(u)) be the shortest distance (in number of portals) from node 1 to (u) and (d_2(v)) the shortest distance from node 2 to (v) (and similarly for (u) and (v) interchanged). The candidate edge may create a new route from 1 to 2 of length (d_1(u) + 1 + d_2(v)) or (d_1(v) + 1 + d_2(u)). The king will only approve the construction if [ \min(d_1(u) + 1 + d_2(v),; d_1(v) + 1 + d_2(u)) \ge 5. ] Your task is to count the number of candidate portals (edge pairs) that satisfy this condition.

Note: If a planet is unreachable from planet 1 or planet 2 in the existing network, treat its distance as (\infty) (which is safe for the purpose of this problem).

inputFormat

The first line contains two integers (N) and (M) representing the number of planets and the number of existing teleportation portals, respectively. Each of the following (M) lines contains two integers (u) and (v) (with (1 \le u, v \le N) and (u \neq v)) indicating that there is a bidirectional portal between planets (u) and (v).

outputFormat

Output a single integer: the number of additional portal constructions the king can approve such that, after adding any one of them to the existing network, any route from planet 1 to planet 2 via new portals will consist of at least 5 portals (i.e. travel time of at least 250 minutes).

sample

3 0

2