Distinct Routes

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 500;
int W[N][N], W2[N][N];
vector<int> V[N];
int n, m;
bool Z[N];

ll dfs(int i, ll c, ll w0) {
  if (i == n-1) {
    return w0;
  }
  if (Z[i]) return 0;
  Z[i] = 1;
  for (int j : V[i]) {
    ll w = W[i][j];
    if (w >= c) {
      ll v = dfs(j,c,min(w0,w));
      if (v) {
        W[i][j] -= v;
        W[j][i] += v;
        return v;
      }
    }
  }
  return 0;
}

int main() {
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    V[a-1].push_back(b-1);
    V[b-1].push_back(a-1);
    W[a-1][b-1] += 1;
    ++W2[a-1][b-1];
  }
  ll ans = 0;
  for (ll c = 1000; c >= 1; c /= 2) {
    while (1) {
      memset(Z,0,n);
      ll w = dfs(0,c,1e18);
      if (w == 0) break;
      ans += w;
    }
  }
  cout << ans << '\n';
  for (int i = 0; i < ans; ++i) {
    vector<int> P;
    P.push_back(0);
    while (P.back() != n-1) {
      int j = P.back();
      for (int k : V[j]) {
        if (W2[j][k] && !W[j][k]) {
          P.push_back(k);
          --W2[j][k];
          ++W[j][k];
          break;
        }
      }
      assert(P.back() != j);
    }
    cout << P.size() << '\n';
    for (int j : P) {
      cout << j+1 << ' ';
    }
    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