#include <bits/stdc++.h>
/*#include <iostream>
#include <climits>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <bitset>
*/
using namespace  std;
#define  int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define fi first
#define se second
#define pb  push_back
#define inf 1ll<<62
#define db double
#define endl "\n"
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define de_bug(x) cerr << #x << "=" << x << endl
#define all(a) a.begin(),a.end()
#define IOS   std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define  fer(i,a,b)  for(int i=a;i<=b;i++)
#define  der(i,a,b)  for(int i=a;i>=b;i--)
const int mod = 1e9 + 7;
const int N = 3e3 + 10;
const int M = 1e5 + 10;

int h[N], e[M], ne[M], w[M];
int cnt;
array<int, 3> g[M];
int n, m;
int vis[N];
int d[N];
int cnt1;
int num[N];
int pre[N];
int ans = (1 << 30);
void add(int a, int b, int c) {
	e[cnt] = b, ne[cnt] = h[a], w[cnt] = c, h[a] = cnt++;
}

void dij(int s, int t) {
	for (int i = 1; i <= n; i++) {
		vis[i] = 0;
		d[i] = (1 << 30);
	}
	priority_queue<pii, vector<pii>, greater<pii>> q;
	q.push({0, s});
	d[s] = 0;
	while (!q.empty()) {
		pii a = q.top();
		int u = a.second;
		q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (int i = h[u]; ~i; i = ne[i]) {
			int v = e[i];
			if(u == s && v == t || u == t && v == s) continue;
			if (d[v] > d[u] + w[i]) {
				d[v] = d[u] + w[i];
				q.push({d[v], v});
			}
		}
	}
}

void bfs(int a, int b) {
	for(int i = 1; i <= n; i++) {
		d[i] = 1 << 30;
		vis[i] = 0;
	}
	queue<int>q;
	q.push(a);
	q.push(b);
	vis[a] = 1;
	vis[b] = 1;
	d[a] = d[b] = 0;
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(int i = h[u]; ~i; i = ne[i]) {
			int v = e[i];
			if(d[v] > d[u] + 1) {
				d[v] = d[u] + 1;
				if(!vis[v]) {
					vis[v] = 1;
					q.push(v);
				}
			} else if(d[v] == ans && d[v] == d[u] + 1 && vis[v]) {
				cnt1++;
			}
		}
	}
}/*
void bfs(int x) {
	//cout<<ans<<endl;
/*	for(int i = 1; i <= n; i++) {
		d[i] = 1 << 30;
	//	vis[i] = 0;
		num[i] = 0;
		pre[i] = 0;
	}
	queue<int>q;
	q.push(x);
	d[x] = 0;
	//vis[x] = 1;
	num[x] = 1;
	while(!q.empty()) {
		int t = q.front();
		q.pop();
		if(d[t] * 2 == ans) {
			cnt1 += 1ll * num[x] * (num[x] - 1) / 2;
		}
		for(int i = h[t]; ~i; i = ne[i]) {
			int v = e[i];
			if(d[v] == 1 << 30) {
				d[v] = d[t] + 1;
				pre[v] = t;
				num[v] = num[t];
			//	if(!vis[v]) {
					q.push(v);
			//		vis[v] = 1;
			//	}
			} /*else if(d[v] == ans && vis[v]  && d[v] == d[t] + 1) {
				cnt1++;
			}*/
//	else if(d[v] == d[t] + 1) {
//		num[v] += num[x];
//	}
//}
//}
//}
void bfs(int t) {
	for(int i = 1; i <= n; i++) {
		d[i] = 1 << 30;
		num[i] = 0;
		pre[i] = 0;
	}
	d[t] = 0, num[t] = 1;
	queue<int> q;
	q.push(t);
	while(!q.empty()) {
		int x = q.front();
		q.pop();
		if(d[x] * 2 == ans) {
			cnt1 += num[x] * (num[x] - 1) / 2;
		}
		for(int i = h[x]; ~i; i = ne[i]) {
			int y = e[i];
			if(d[y] == 1 << 30) {
				d[y] = d[x] + 1;
				pre[y] = x;
				num[y] = num[x];
				q.push(y);
			} else if(d[y] == d[x] + 1) {
				num[y] += num[x];
			}
		}
	}
}
void  solve() {
	cin >> n >> m;
	memset(h, -1, sizeof(h));
	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b ;
		add(a, b, 1);
		add(b, a, 1);
		g[i] = {a, b, 1};
	}

	for (int i = 1; i <= m; i++) {
		int a = g[i][0];
		int b = g[i][1];
		int c = g[i][2];
		dij(a, b);
		ans = min(ans, d[b] + c);
	}
	//cout << ans << endl;
	int tmp = ans;
	if(ans % 2 == 0) {
		//ans /= 2;
	} else ans = (ans - 1) / 2;
	if(tmp % 2 == 1) {
		for (int i = 1; i <= m; i++) {
			int a = g[i][0];
			int b = g[i][1];
			bfs(a, b);
		}

	} else {
		for(int i = 1; i <= n; i++) {
			bfs(i);
		}
		//cout << cnt1 << endl;
	}
	//cout<<cnt1<<endl;
	/*for(int i = 1; i <= n; i++) {
		cout << d[i] << endl;
	}*/
	cout << cnt1 / tmp << endl;

}

signed main() {
	IOS;
	int _ = 1;
	//cin>>_;
	while( _-- )
		solve();
	return 0;
}

/*
9 12
1 2
2 3
4 5
5 6
7 8
8 9
1 4
2 5
3 6
4 7
5 8
6 9

*/