# CFR 645 D. Robot Rapping Results Report ( Graph, TopoSort, Binary Search )

Problem - 645D - Codeforces

1 ≤ N ≤ 1e5
1 ≤ M ≤ 1e5

O( N lg M ) / O( N )

```const int MOD7 = ( int ) 1e9 + 7;

int N, M;
vp edge;

void init(){
cin >> N >> M;
edge = vp( M );
for( int i = 0; i < M; ++i ){
int u, v; cin >> u >> v; --u, --v;
edge[ i ] = make_pair( u, v );
}
}

void topo_sort( int u, const vvi &g, vi &sorted, vi &vis ){
for( int v : g[ u ] ){
if( vis[ v ] ) continue;
vis[ v ] = 1;
topo_sort( v, g, sorted, vis );
}
sorted.emplace_back( u );
}

int ok( int x ){
unordered_set< ll > has_edge;
vvi g( N );
for( int i = 0; i < x; ++i ){
has_edge.emplace( 1LL * MOD7 * edge[ i ].first + edge[ i ].second );
g[ edge[ i ].first ].emplace_back( edge[ i ].second );
}
vi sorted;
vi vis( N );
for( int i = 0; i < N; ++i ){
if( vis[ i ] ) continue;
vis[ i ] = 1;
topo_sort( i, g, sorted, vis );
}
for( int i = 0; i + 1 < sorted.size(); ++i ){
if( not has_edge.count( 1LL * MOD7 * sorted[ i + 1 ] + sorted[ i ] ) ){
return 0;
}
}
return 1;
}

void preprocess(){
int ans = -1;
for( int lb = 1, rb = M; lb <= rb; ){
int mid = lb + rb >> 1;
if( ok( mid ) ){
ans = mid;
rb = mid - 1;
} else{
lb = mid + 1;
}
}
cout << ans << endl;
}
```