Proficient.
Put your skills to the test.

Problem summary

Reverse any chosen directed connections so that the resulting graph has no directed cycle. Return one binary decision per edge; minimizing reversals is not required.

Source clarification. The original problem uses a grader interface rather than ordinary stdin/stdout. This page preserves that interface and supplies an explicitly labeled local demonstration driver. The output need not match the sample’s particular valid orientation.

Constraints

3≤N≤500000; 3≤M≤1500000; vertices1..N; no self-loops, duplicate edges or antiparallel edge pairs.

Worked example

Original statement sample.

6 12
1 2
1 5
2 3
2 5
3 4
3 6
4 1
4 5
5 3
5 6
6 1
6 4

000000101011

Solution analysis

1. Choose a fixed total ordering of the vertices:1,2,…,N. Make every edge point from the smaller endpoint to the larger endpoint. For an original edge u→v, reverse it exactly when u>v.
2. No graph search or minimum-feedback-edge optimization is needed because the statement accepts any number of reversals. The total order itself supplies a topological ordering.
3. In the worked input, reverse4→1,5→3,6→1 and6→4. All remaining arrows then increase the vertex number. The displayed string is a different valid answer from the original example’s choice.

Why it works

Along every resulting directed edge, the vertex number strictly increases. A directed cycle would force a strict increase all the way back to its starting number, which is impossible. Hence the returned decisions always produce a DAG.

Watch out. The original submission is a function, not a standalone stdin program. Do not optimize the number of reversed edges unnecessarily. Preserve input-edge order when constructing the string.

Compile the complete local demonstration with g++ -std=c++17 -DLOCAL. Without LOCAL only the judge function find_reverse is compiled; submit it to the original grader, which supplies main and the input.

#include<iostream>
#include<string>
using namespace std;
string find_reverse(int n,int m,int connections[][2]){
    (void)n;
    string result(m,'0');
    for(int edge=0;edge<m;edge++){
        // All final arrows point from a smaller label to a larger label.
        if(connections[edge][0]>connections[edge][1]){
            result[edge]='1';
        }
    }
    return result;
}
#ifdef LOCAL
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    int(*connections)[2]=new int[m][2];
    for(int edge=0;edge<m;edge++){
        cin>>connections[edge][0]>>connections[edge][1];
    }
    cout<<find_reverse(n,m,connections)<<'\n';
    delete[]connections;
}
#endif