Shared code

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
vector<int> parent;

ll f(vector<vector<ll>> &cap, int s, int t, vector<int> adj[]){
    parent.assign(t+1, -1);
    queue<pair<ll, ll>> q;
    q.push({s, 1e9});
    parent[s] = -2;

    while(!q.empty()){
        auto [node, flow] = q.front(); q.pop();
        for(auto &child: adj[node]){
            if(parent[child]==-1 and cap[node][child]>0){
                parent[child] = node;
                int nflow= min(flow, cap[node][child]);
                if(child==t) return nflow;
                q.push({child, nflow});
            }
        }
    }
    return 0;
}

int main(){
    int n, m; cin>>n>>m;
    vector<vector<ll>> cap(n+1, vector<ll>(n+1, 0));
    vector<int> adj[n+1];
    for(int i=0; i<m; i++){
        ll u, v; cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        cap[u][v] += 1;
        cap[v][u] += 1;
    }

    ll maxFlow = 0;
    ll curr = 0;
    parent.resize(n+1);
    while(true){
        curr = f(cap, 1, n, adj);
        if(curr==0) break;
        maxFlow+=curr;
        int nd = n;
        while(nd!=1){
            cap[parent[nd]][nd] -= curr;
            cap[nd][parent[nd]] += curr;
            nd = parent[nd];
        }
    }

    vector<bool> vis(n+1, false);
    queue<int> q; q.push(1); vis[1] = true;
    while(!q.empty()){
        int node = q.front(); q.pop();
        for(int i=1;i<=n;i++){
            if(!vis[i] && cap[node][i]>0){
                vis[i] = true;
                q.push(i);
            }
        }
    }


    cout<<maxFlow<<endl;

    for(int i=1;i<=n;i++){
        if(!vis[i]) continue;
        for(auto &child: adj[i]){
            if(vis[child]) continue;
            cout<<i<<" "<<child<<endl;
        }
    }

    return 0;
}