Expert.
Put your skills to the test.

Problem summary

Partition all edges of a connected simple undirected graph into the minimum number of trails. A trail may revisit vertices but not edges, and may be closed. Output the trails as stop sequences. Transfers between trails at common stops are allowed.

Constraints

2 ≤ N ≤ 50,000; 1 ≤ M ≤ 100,000; connected graph; no loops or repeated edges.

Worked example

Independently chosen example; this is one optimal output, and other route orientations are valid.

3 2
1 2
2 3

1
3 1 2 3

Solution analysis

1. Let o be the number of odd-degree vertices. Every open trail contributes two odd endpoint incidences, so at least o/2 trails are required if o>0. If o=0, a single Euler circuit suffices. Thus the answer is max(1,o/2).
2. When odd vertices exist, introduce one auxiliary vertex 0 and connect it to every odd vertex. All degrees become even, so iterative Hierholzer traversal finds an Euler circuit starting at 0. Remove vertex 0 and its incident auxiliary edges from the circuit; the remaining consecutive pieces are the desired original-edge trails. With no odd vertices, run Hierholzer directly from vertex 1.
3. For the path 1−2−3, vertices 1 and 3 are odd. Adding 0−1 and 0−3 makes the circuit 0,1,2,3,0. Removing the auxiliary edges leaves exactly the trail 1,2,3. The example is an independently chosen instance with a valid optimal output.

Why it works

In any decomposition, an odd-degree vertex must be an endpoint an odd number of times, establishing the o/2 lower bound. The augmented graph is connected and all its degrees are even, so Hierholzer uses every edge exactly once in an Euler circuit. Each excursion from auxiliary vertex 0 uses two auxiliary edges; there are exactly o/2 excursions. Removing these edges yields that many nonempty original trails covering all original edges once. In the even case, the original Euler circuit achieves the lower bound one. Connectivity of their union ensures transfers remain possible.

Watch out. Use edge identifiers to mark both directed adjacency entries used together. Output vertex counts, which are one larger than edge counts. Avoid recursive traversal at these bounds.

An independently written complete program with standard headers.

// Key idea: In any decomposition, an odd-degree vertex must be an endpoint an odd number of times,
// establishing the o/2 lower bound. The augmented graph is connected and all its degrees are even, so
// Hierholzer uses every edge exactly once in an Euler circuit.
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<vector<pair<int,int>>>graph(n+1);
    int edges=0;
    auto addEdge=[&](int u,int v){
        graph[u].push_back({v,edges});
        graph[v].push_back({u,edges++});
    };
    for(int i=0;i<m;++i){
        int u,v;
        cin>>u>>v;
        addEdge(u,v);
    }
    vector<int>odd;
    for(int v=1;v<=n;++v){
        if(graph[v].size()%2){
            odd.push_back(v);
        }
    }
    for(int v:odd){
        addEdge(0,v);
    }
    vector<bool>used(edges,false);
    vector<int>next(n+1),stack={odd.empty()?1:0},tour;
    while(!stack.empty()){
        int v=stack.back();
        while(next[v]<int(graph[v].size())&&used[graph[v][next[v]].second]){
            ++next[v];
        }
        if(next[v]==int(graph[v].size())){
            tour.push_back(v);
            stack.pop_back();
        }
        else{
            auto[u,id]=graph[v][next[v]++];
            used[id]=true;
            stack.push_back(u);
        }
    }
    reverse(tour.begin(),tour.end());
    vector<vector<int>>routes;
    if(odd.empty()){
        routes.push_back(tour);
    }
    else{
        vector<int>current;
        for(int v:tour){
            if(v==0){
                if(!current.empty()){
                    routes.push_back(current);
                    current.clear();
                }
            }
            else{
                current.push_back(v);
            }
        }
    }
    cout<<routes.size()<<'\n';
    for(const auto&route:routes){
        cout<<route.size();
        for(int v:route){
            cout<<' '<<v;
        }
        cout<<'\n';
    }
}