#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'

int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	int n, m;
    cin >> n >> m;
    n *= 2;
    vector<unordered_set<int>> adj(n+1);
    vector<array<int,2>> edges(m);
    for(int i=0; i<m; i++){
        int a, b;
        cin >> a >> b;
        adj[a].insert(b);
        adj[b].insert(a);
        edges[i] = {a,b};
    }
    
    bool found=0;
    
    for(int u=1; u<=n && !found; u++){
    	for(int v=1; v<=n && !found; v++){
    		if(u==v) continue;
    		bool ok = 0;
    		if(adj[u].size() < adj[v].size()){
    			for(int x : adj[u]){
    				if(adj[v].count(x)){
    					if(ok) found = 1;
    					ok = true;
    				}
    			}
    		}
    		else{
    			for(int x : adj[v]){
    				if(adj[u].count(x)){
    					if(ok) found = 1;
    					ok = true;
    				}
    			}
    		}
    	}
    }
    
    cout << (found ? 2 : 3);
}