// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

int main() {
	cin.tie(0) -> sync_with_stdio(0);

	int N, M; cin >> N >> M;

	vector<vector<int>> adj(2 * N);

	for (int i = 0; i < M; i++) {
		int a, b; cin >> a >> b; a--; b--;

		adj[a].push_back(b); adj[b].push_back(a);
	}

	bool visited[2 * N][2 * N];

	for (int i = 0; i < 2 * N; i++) {
		for (int j = 0; j < 2 * N; j++) {
			visited[i][j] = false;
		}
	}

	for (int i = 0; i < 2 * N; i++) {
		for (auto j : adj[i]) {
			for (auto k : adj[i]) {
				if (j == k) {
					continue;
				}

				if (visited[j][k]) {
					cout << 2 << "\n";
					return 0;
				}

				visited[j][k] = true;
			}
		}
	}

	cout << 3 << "\n";
}