Distinct Routes

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

int n, m;
struct Edge {
    int to;
    int cost;
};
vector<Edge> edges;
vector<vector<int>> adj;
vector<vector<pair<int, bool>>> adj2;
vector<char> vis;
vector<int> path;

void add_edge(int a, int b) {
    adj[a].push_back(edges.size());
    edges.push_back({b, 1});
    adj[b].push_back(edges.size());
    edges.push_back({a, 0});
    adj2[a].push_back({(int)edges.size(), false});
}

ll dfs(int node, int threshold, int flow) {

    if (node == n)
        return flow;

    vis[node] = 1;

    for (int e : adj[node]) {
        Edge &edge = edges[e];

        if (edge.cost < threshold || vis[edge.to])
            continue;

        ll val = dfs(edge.to, threshold, min(flow, edge.cost));
        if (val > 0) {
            edge.cost -= val;
            edges[e ^ 1].cost += val;
            return val;
        }
    }
    return 0;
}

bool simple_dfs(int node, int lenght) {

    if (node == n) {
        cout << lenght << "\n";
        return true;
    }

    vis[node] = 1;

    for (auto &to : adj2[node]) {
        Edge &edge = edges[to.first];

        if (to.second || edge.cost != 0 || vis[edge.to])
            continue;

        if (simple_dfs(edge.to, lenght + 1)) {
            path.push_back(edge.to);
            to.second = true;
            return true;
        }
    }
    return false;
}

ll find() {
    fill(vis.begin(), vis.end(), 0);
    return dfs(1, 1, 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    adj = vector<vector<int>>(n + 1);
    adj2 = vector<vector<pair<int, bool>>>(n + 1);
    vis.assign(n + 1, 0);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        add_edge(a, b);
    }

    ll flow = -1;
    ll val = 1;

    while (val > 0) {
        flow += val;
        val = find();
    }
    cout << flow << "\n";

    fill(vis.begin(), vis.end(), 0);
    while (simple_dfs(1, 1)) {
        cout << 1 << " ";
        for (int i = path.size() - 1; i >= 0; i--) {
            cout << path[i] << " ";
        }
        path = vector<int>();
        cout << "\n";
        fill(vis.begin(), vis.end(), 0);
    }

    return 0;
}

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: ACCEPTED

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: ACCEPTED

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: WRONG ANSWER

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: WRONG ANSWER