//============================================================================
// Name        : I.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include<stdio.h>
#include<vector>
#include<memory.h>
#define N 200
using namespace std;
vector<int> graph[N];
vector<int> tmp;
int sstack[N], pathstack[N], dfsn[N];
int ptop, cnt, stop;
int mark[N], cntt[N];
int color;
int i, n, ans, res, m, u, v, j;
void init() {
	memset(dfsn, -1, sizeof(dfsn));
	memset(mark, -1, sizeof(mark));
	ptop = cnt = stop = color = 0;
}
void Gabow(int w) {
	int v, i;
	dfsn[w] = cnt++;
	sstack[stop++] = pathstack[ptop++] = w;
	for (i = 0; i < graph[w].size(); ++i) {
		v = graph[w][i];
		if (dfsn[v] == -1)
			Gabow(v);
		else if (mark[v] == -1)
			while (dfsn[pathstack[ptop - 1]] > dfsn[v])
				ptop--;
	}
	if (pathstack[ptop - 1] == w)
		ptop--;
	else
		return;
	do {
		mark[v = sstack[--stop]] = color;
	} while (v != w);
	color++;
}

int main() {
	while (scanf("%d%d", &n, &m) != EOF) {
		ans = 10001;
		for (i = 0; i < n; i++)
			graph[i].clear();
		while (m--) {
			scanf("%d%d", &u, &v);
			graph[u].push_back(v);
		}
		for (i = 0; i < n; i++) {
			memset(cntt, 0, sizeof(cntt));
			tmp = graph[i];
			graph[i].clear();
			init();
			Gabow((i + 1) % n);
			res = 0;
			for (i = 0; i < n; i++) {
				if (mark[i] >= 0)
					cntt[mark[i]]++;
				res = max(res, cntt[mark[i]]);
			}
			if (res < ans)
				ans = res;
			graph[i] = tmp;
		/*	for (i = 0; i < n; i++)
				printf("%d ", mark[i]);
			printf("\n");*/
		}
		if (ans != 1)
			printf("%d\n", ans);
		else
			printf("0\n");
	}

	return 0;
}
/*
 5 4
 1 2
 2 1
 3 4
 4 3
 */