Distinct Routes

#include <iostream>
#include <vector>
using namespace std;

int n, m;
vector<int> to, cap;
vector<vector<int>> adj;
vector<bool> vis;

bool dfs(int u) {
    if (u == n) return true;
    vis[u] = true;
    for (int e : adj[u]) {
        if (cap[e] > 0 && !vis[to[e]] && dfs(to[e])) {
            cap[e]--;
            cap[e ^ 1]++;
            return true;
        }
    }
    return false;
}

int main() {
    cin >> n >> m;
    adj.resize(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(to.size());
        to.push_back(b);
        cap.push_back(1);
        adj[b].push_back(to.size());
        to.push_back(a);
        cap.push_back(0);
    }
    int k = 0;
    while (true) {
        vis.assign(n + 1, false);
        if (!dfs(1)) break;
        k++;
    }
    cout << k << "\n";
    for (int d = 0; d < k; d++) {
        vector<int> path = {1};
        int u = 1;
        while (u != n) {
            for (int e : adj[u]) {
                if (e % 2 == 0 && cap[e] == 0) {
                    cap[e] = 1;
                    u = to[e];
                    break;
                }
            }
            path.push_back(u);
        }
        cout << path.size() << "\n";
        for (int v : path) cout << v << " ";
        cout << "\n";
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED