2316

#include <bits/stdc++.h>
using namespace std;
 
#define FAST_IO                  \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);
 
struct EdmondsKarp {
    struct Edge {
        int to, rev, cap;
    };
 
    int n;
    vector<vector<Edge>> g;
 
    EdmondsKarp(int n = 0)
        : n(n), g(n) {}
 
    void addEdge(int v, int u, int c) {
        Edge a { u, (int)g[u].size(), c };
        Edge b { v, (int)g[v].size(), 0 };
        g[v].push_back(a);
        g[u].push_back(b);
    }
 
    int maxflow(int s, int t) {
        int flow = 0;
 
        while (true) {
            vector<int> pv(n, -1), pe(n, -1);
            queue<int> q;
 
            pv[s] = s;
            q.push(s);
 
            while (!q.empty() && pv[t] == -1) {
                int v = q.front();
                q.pop();
 
                for (int i = 0; i < (int)g[v].size(); ++i) {
                    Edge& e = g[v][i];
 
                    if (e.cap <= 0 || pv[e.to] != -1) {
                        continue;
                    }
 
                    pv[e.to] = v;
                    pe[e.to] = i;
                    q.push(e.to);
 
                    if (e.to == t) {
                        break;
                    }
                }
            }
 
            if (pv[t] == -1) {
                break;
            }
 
            int add = INT_MAX;
 
            for (int v = t; v != s; v = pv[v]) {
                Edge& e = g[pv[v]][pe[v]];
                add = min(add, e.cap);
            }
 
            for (int v = t; v != s; v = pv[v]) {
                Edge& e = g[pv[v]][pe[v]];
                e.cap -= add;
                g[e.to][e.rev].cap += add;
            }
 
            flow += add;
        }
 
        return flow;
    }
};
 
int main() {
    FAST_IO;
 
    int N, P;
    cin >> N >> P;
 
    const int INF = 1'000'000'000;
 
    auto IN = [](int x) {
        return x * 2;
    };
 
    auto OUT = [](int x) {
        return x * 2 + 1;
    };
 
    EdmondsKarp mf(2 * N + 2);
 
    for (int city = 1; city <= N; ++city) {
        if (city == 1 || city == 2) {
            mf.addEdge(IN(city), OUT(city), INF);
        } else {
            mf.addEdge(IN(city), OUT(city), 1);
        }
    }
 
    for (int i = 0; i < P; ++i) {
        int a, b;
        cin >> a >> b;
 
        mf.addEdge(OUT(a), IN(b), INF);
        mf.addEdge(OUT(b), IN(a), INF);
    }
 
    cout << mf.maxflow(OUT(1), IN(2)) << '\n';
 
    return 0;
}