#include <bits/stdc++.h>
#define dd(x) cout << #x << "\n"
#define d(x) cout << #x  << ": " << x << "\n"
using namespace std;
#define int long long
using pii = pair<int, int>;
using vpii = vector<pii>;
using vi = vector<int>;
using vii = vector<vector<int>>;
using a3 = array<int, 3>;
const int inf = 0x3f3f3f3f3f3f3f3fLL;

const int N = 1e6 + 6;
int col[N], used[N];
int n, m, ans;
vector<pair<int, int>> adj[N];

int dfs(int u, int fr, int edgId) {
    if(u == n) {
        ++ans; used[edgId] = 1;
        return true;
    }

    for(auto [v, id] : adj[u]) {
        if(v == fr) continue;
        if(used[id]) continue;
        if(col[v]) continue;

        if(dfs(v, u, id)) {
            col[u] = 1;
            used[id] = 1;
            return true;
        }
    }
    return false;
}

void solve() {
    cin >> n >> m;
    vector<pair<int, int>> edg(m + 1);
    for(int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        edg[i].first = u, edg[i].second = v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    while(dfs(1, 0, 0)) {
        col[1] = 0; col[n] = 0;
    }

    for(int i = 1; i <= m; i++) {
        if(used[i]) continue;
        if((col[edg[i].first] && col[edg[i].second])) ++ans;
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    while(T--) solve();
    return 0;
}

/*
5 7
1 3
3 5
1 2
2 3
3 4
4 5
2 4

*/