// 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);
	}

	set<pair<int, int>> visited;

	for (int i = 0; i < 2 * N; i++) {
		for (auto j : adj[i]) {
			for (auto k : adj[i]) {
				if (j == k) {
					continue;
				}
				
				if (visited.count({j, k})) {
					cout << 2 << "\n";
					return 0;
				}

				visited.insert({j, k});
			}
		}
	}

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