17412

#if defined(__GNUC__) && defined(__x86_64__)
#    pragma GCC optimize("O3")
#    pragma GCC optimize("Ofast")
#    pragma GCC optimize("unroll-loops")
#    pragma GCC target("avx,avx2,fma")
#endif
 
#include <bits/stdc++.h>
using namespace std;
 
#ifdef LOCAL
#    define LOG clog
#else
struct nullstream : ostream {
    nullstream()
        : ostream(nullptr) {}
};
nullstream LOG;
#endif
 
//--//--//--//--//--//--//--//--//--//--//--//--//--//--//--//--//--//--//--//--//--//--//--//--//--
 
#define FAST_IO                  \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);
 
#define END return 0;
 
using LL  = long long;
using ULL = unsigned long long;
 
[[maybe_unused]]
constexpr int _MAX
    = 1'234'567'891;
 
[[maybe_unused]]
constexpr int _MIN
    = -_MAX;
 
[[maybe_unused]]
constexpr LL __MAX
    = 1'111'111'111'111'111'111LL;
 
[[maybe_unused]]
constexpr LL __MIN
    = -__MAX;
 
//--------------------------------------------------------------------------------------------------
 
// solution
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);
    }
 
    bool bfs(int s, int t, vector<int>& parentVertex, vector<int>& parentEdge) {
        fill(parentVertex.begin(), parentVertex.end(), -1);
        fill(parentEdge.begin(), parentEdge.end(), -1);
 
        queue<int> q;
 
        parentVertex[s] = s;
        q.push(s);
 
        while (!q.empty()) {
            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 || parentVertex[e.to] != -1) {
                    continue;
                }
 
                parentVertex[e.to] = v;
                parentEdge[e.to]   = i;
 
                if (e.to == t) {
                    return true;
                }
 
                q.push(e.to);
            }
        }
 
        return false;
    }
 
    int maxflow(int s, int t) {
        int flow = 0;
 
        vector<int> parentVertex(n);
        vector<int> parentEdge(n);
 
        while (bfs(s, t, parentVertex, parentEdge)) {
            int amount = INT_MAX;
 
            for (int cur = t; cur != s; cur = parentVertex[cur]) {
                int prev = parentVertex[cur];
                int idx  = parentEdge[cur];
 
                amount = min(amount, g[prev][idx].cap);
            }
 
            for (int cur = t; cur != s; cur = parentVertex[cur]) {
                int prev = parentVertex[cur];
                int idx  = parentEdge[cur];
 
                Edge& e = g[prev][idx];
 
                e.cap -= amount;
                g[e.to][e.rev].cap += amount;
            }
 
            flow += amount;
        }
 
        return flow;
    }
};
 
/* 1. 이 문제를 푸는 한줄 핵심
- 각 단방향 도로를 용량 1로 둔 최대 유량으로 1번 도시에서 2번 도시까지 서로 간선을 공유하지 않는 경로 수를 센다.
*/
 
/* 2. 단계별 접근 과정 요약 (5줄 이내)
- 입력 도로마다 같은 방향 용량 1 간선을 추가해 한 도로가 한 번만 쓰이게 한다.
- 소스는 1번, 싱크는 2번 도시로 둔다.
- Edmonds-Karp는 BFS로 최단 증가 경로를 하나씩 찾는다.
- 증가 경로를 찾을 때마다 병목 용량만큼 유량을 흘린다.
- 더 이상 증가 경로가 없으면 최대 유량 값을 출력한다.
*/
 
int main() {
    FAST_IO;
 
    int N, P;
    cin >> N >> P;
 
    EdmondsKarp ek(N + 1);
 
    for (int i = 0, a, b; i < P; ++i) {
        cin >> a >> b;
        ek.addEdge(a, b, 1);
    }
 
    cout << ek.maxflow(1, 2) << '\n';
 
    END;
}