Shared code

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<cstring>
 
using namespace std;
int n,m;
int par[501],graph[501][501],orig[501][501];
bool vis[501],vis2[501][501];
bool bfs(){
queue<int>que;
int u=1;
memset(vis,0,sizeof vis);
que.push(u);
while(!que.empty()){
u=que.front();
que.pop();
if(vis[u])continue;
vis[u]=true;
  for(int v=2;v<=n;v++){
    if(!vis[v] and graph[u][v]>0){
      par[v]=u; 
      que.push(v);
    }
  }
}
return vis[n];
}
bool find(){
queue<int>que;
int u=1;
memset(vis,0,sizeof vis);
que.push(u);
while(!que.empty()){
u=que.front();
que.pop();
if(vis[u])continue;
vis[u]=true;
  for(int v=2;v<=n;v++){
    if(!vis[v] and !vis2[u][v] and graph[u][v]==0 and orig[u][v]){
      par[v]=u; 
      que.push(v);
    }
  }
}
return vis[n];
}
int main(){
  cin>>n>>m;
  int a,b;
  for(int i=0;i<m;i++){
    cin>>a>>b;
    graph[a][b]=1;
    orig[a][b]=1;
  }
  int cnt=0;
  while(bfs()){  
     a=n;
     cnt++;
     while(a!=1){
      graph[par[a]][a]--;
      graph[a][par[a]]++;
      a=par[a];
     }
  } 
  cout<<cnt<<endl;
  memset(vis,0,sizeof vis);
  for(int i=1;i<=cnt;i++){
    vector<int>ans;
    find();
     a=n;
     while(a!=1){
      ans.push_back(a);
      vis2[par[a]][a]=true;
      a=par[a];
     }
     ans.push_back(1);
    reverse(ans.begin(),ans.end());
    cout<<ans.size()<<endl;
    for(int num:ans)cout<<num<<" ";
    cout<<endl;    
  }
  return 0;
}