Expert.
Put your skills to the test.

Problem summary

Orient every edge of an undirected graph so that each vertex has incoming and outgoing degrees differing by at most one. Print a valid orientation.

Constraints

1≤N≤1000;1≤M≤100000;each unordered pair occurs at most once.

Worked example

An independently prepared worked example; constructive outputs may have other valid forms.

3 2
1 2
2 3

Yes
1 2
2 3

Solution analysis

1. A closed Euler tour enters and leaves each vertex equally often. Therefore an all-even-degree graph can be oriented by following its Euler tours.
2. Add a temporary vertex0 and connect it once to every original odd-degree vertex. The number of odd vertices is even, so every degree, including vertex0, is now even. Orient each connected component by an Euler traversal, then omit the temporary edges.
3. For the path1–2–3, vertices1 and3 receive temporary edges to0. A tour0→1→2→3→0 gives original orientations1→2 and2→3. Removing the temporary edge changes each odd vertex’s degree balance by exactly one.

Why it works

The augmented graph has only even degrees and each Euler traversal gives zero degree balance. An original even vertex loses no edges; an odd vertex loses one temporary edge, leaving balance+1 or−1. Thus the construction always succeeds, even for disconnected graphs.

Watch out. Preserve edge identities when skipping used undirected edges. Start a traversal in every nonempty component. Temporary edges must never be printed.

An independently written complete program with standard headers.

#include<iostream>
#include<utility>
#include<vector>
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);
    vector<pair<int,int>>answer(m);
    int edges=0;
    auto addEdge=[&](int a,int b){
        graph[a].push_back({b,edges});
        graph[b].push_back({a,edges});
        edges++;
    };
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        addEdge(a,b);
    }
    for(int v=1;v<=n;v++){
        if(graph[v].size()%2==1){
            addEdge(0,v);
        }
    }
    vector<bool>used(edges);
    vector<int>next(n+1);
    for(int start=0;start<=n;start++){
        vector<int>stack{start};
        while(!stack.empty()){
            int v=stack.back();
            while(next[v]<static_cast<int>(graph[v].size())&&used[graph[v][next[v]].second]){
                next[v]++;
            }
            if(next[v]==static_cast<int>(graph[v].size())){
                stack.pop_back();
                continue;
            }
            auto[to,id]=graph[v][next[v]++];
            used[id]=true;
            // Orient original edges in traversal direction.
            if(id<m){
                answer[id]={v,to};
            }
            stack.push_back(to);
        }
    }
    cout<<"Yes\n";
    for(auto[a,b]:answer){
        cout<<a<<' '<<b<<'\n';
    }
}