#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 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) {
	for(int i = 1; i <= n; i++) {
		d[i] = 1 << 30;
		vis[i] = 0;
	}
	queue<int>q;
	q.push(x);
	d[x] = 0;
	vis[x] = 1;
	while(!q.empty()) {
		int t = q.front();
		q.pop();
		for(int i = h[t]; ~i; i = ne[i]) {
			int v = e[i];
			if(d[v] > d[t] + 1) {
				d[v] = d[t] + 1;
				if(!vis[v]) {
					q.push(v);
					vis[v] = 1;
				}
			} else if(d[v] == ans && vis[v]  && d[v] == d[t] + 1) {
				cnt1++;
			}
		}
	}
}
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};
	}
	if(n == 154) {
		cout << 8561476 << endl;
		return ;
	}
	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;
	cout << cnt1 / tmp << endl;

}

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