Proficient.
Put your skills to the test.

Problem summary

A complete double-M domino set contains every unordered pair {a,b} with0≤a≤b≤M, including doubles. After removing the listed tiles, arrange every remaining tile into as few chains as possible. Print those chains as endpoint sequences ending with−1.

Constraints

0 ≤ M ≤1024; not every tile is removed.

Worked example

Original statement sample input; one valid output from the implementation below.

3 5
0 2
1 1
1 2
1 3
3 3

1
2 2 3 0 0 1 -1

Solution analysis

1. Make a graph whose vertices are labels0…M and whose edges are remaining tiles. A double is a self-loop and contributes2 to its vertex’s degree. A domino chain is exactly an edge-disjoint trail. Each nonempty connected component with o odd vertices needs max(1,o/2) trails.
2. Add one temporary vertex connected to every odd-degree vertex. Every affected component now has only even degrees and joins this temporary vertex. Run iterative Hierholzer from it, then split the resulting circuit whenever the temporary vertex appears. Removing those artificial edges leaves exactly o/2 trails in each odd component.
3. Components with no odd vertices do not touch the temporary vertex; run one ordinary Euler circuit in each of them. Isolated label vertices with no tiles are ignored. The sample leaves five edges, forming one chain2,2,3,0,0,1. Its doubled2 and doubled0 are ordinary self-loop tiles, not repeated uses of another edge.

Why it works

Every trail has at most two odd endpoints, so a component with o odd vertices needs at least o/2 trails; a nonempty even component needs at least one. The artificial-vertex Euler circuit uses every original edge once. Splitting at artificial edges produces exactly o/2 trails in odd components, while an even component yields one circuit. Thus the lower bound is attained and all remaining tiles are used exactly once.

Watch out. A loop contributes degree2. Give each tile one edge ID even though adjacency stores it twice. Normalize removed pairs because{a,b} and{b,a} are the same tile. Do not count unused labels as chains.

An independently written complete program with standard headers.

// Key idea: Every trail has at most two odd endpoints, so a component with o odd vertices needs at
// least o/2 trails; a nonempty even component needs at least one. The artificial-vertex Euler circuit
// uses every original edge once.
#include<algorithm>
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int maximum,removedCount;
    cin>>maximum>>removedCount;
    int vertices=maximum+1;
    int extra=vertices;
    vector<bool>removed(static_cast<size_t>(vertices)*vertices,false);
    for(int i=0;i<removedCount;++i){
        int a,b;
        cin>>a>>b;
        if(a>b){
            swap(a,b);
        }
        removed[static_cast<size_t>(a)*vertices+b]=true;
    }
    vector<vector<pair<int,int>>>graph(vertices+1);
    vector<int>degree(vertices);
    vector<bool>used;
    auto addEdge=[&](int a,int b){
        int id=static_cast<int>(used.size());
        used.push_back(false);
        graph[a].push_back({b,id});
        graph[b].push_back({a,id});
    };
    for(int a=0;a<vertices;++a){
        for(int b=a;b<vertices;++b){
            if(!removed[static_cast<size_t>(a)*vertices+b]){
                addEdge(a,b);
                ++degree[a];
                ++degree[b];
            }
        }
    }
    for(int a=0;a<vertices;++a){
        if(degree[a]%2==1){
            addEdge(extra,a);
        }
    }
    auto euler=[&](int start){
        vector<int>pending{start},circuit;
        while(!pending.empty()){
            int u=pending.back();
            while(!graph[u].empty()&&used[graph[u].back().second]){
                graph[u].pop_back();
            }
            if(graph[u].empty()){
                circuit.push_back(u);
                pending.pop_back();
            }
            else{
                auto[v,id]=graph[u].back();
                graph[u].pop_back();
                used[id]=true;
                pending.push_back(v);
            }
        }
        reverse(circuit.begin(),circuit.end());
        return circuit;
    };
    vector<vector<int>>trails;
    if(!graph[extra].empty()){
        vector<int>path=euler(extra);
        vector<int>current;
        for(int vertex:path){
            if(vertex==extra){
                if(current.size()>=2){
                    trails.push_back(current);
                }
                current.clear();
            }
            else{
                current.push_back(vertex);
            }
        }
    }
    for(int start=0;start<vertices;++start){
        while(!graph[start].empty()&&used[graph[start].back().second]){
            graph[start].pop_back();
        }
        if(!graph[start].empty()){
            trails.push_back(euler(start));
        }
    }
    cout<<trails.size()<<'\n';
    for(const vector<int>&trail:trails){
        for(int vertex:trail){
            cout<<vertex<<' ';
        }
        cout<<-1<<'\n';
    }
}