Guest User

CF D

a guest
Mar 18th, 2016
114
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //==================================================================//
  2. // Name        : flash7even                                         //
  3. // Author      : Tarango Khan                                       //
  4. // Codeforces  : flash_7                                            //
  5. // Topcoder    : flash_7                                            //
  6. // Hackerrank  : flash_7                                            //
  7. // Email       : tarangokhan77@gmail.com                            //
  8. // Facebook    : tarango.khan                                       //
  9. //==================================================================//
  10.  
  11. //==================================================================//
  12. #include <bits/stdc++.h>                                            //
  13. using namespace std;                                                //
  14. #define read(nm)        freopen(nm, "r", stdin)                     //
  15. #define write(nm)       freopen(nm, "w", stdout)                    //
  16. #define pb              push_back                                   //
  17. #define mp              make_pair                                   //
  18. #define F               first                                       //
  19. #define S               second                                      //
  20. #define eps             1e-9                                        //
  21. #define FABS(x)         ((x)+eps<0?-(x):(x))                        //
  22. #define pf              printf                                      //
  23. #define sf              scanf                                       //
  24. #define pi              acos(-1.0)                                  //
  25. #define SZ(x)           ((int)(x).size())                           //
  26. #define mems(x,v)       memset(x,v,sizeof(x))                       //
  27. #define fills(v,n)      fill(v.begin(), v.end(), n)                 //
  28. #define vsort(v)        sort(v.begin(),v.end())                     //
  29. #define asort(v,n)      sort(a,a+n)                                 //
  30. #define LL              long long                                   //
  31. #define LLU             long long unsigned int                      //
  32. #define vu_bound(v,a)   upper_bound(v.begin(),v.end(),a)-v.begin()  //
  33. #define vl_bound(v,a)   lower_bound(v.begin(),v.end(),a)-v.begin()  //
  34. #define fast_cin ios_base::sync_with_stdio(false);cin.tie(NULL)     //
  35. //==================================================================//
  36.  
  37. //==================================================================//
  38. void make_unique(vector<int> &a){ sort(a.begin(), a.end());         //
  39.      a.erase(unique(a.begin(), a.end()), a.end()); }                //
  40. int  Set(int N,int cur){ return N = N | (1<<cur); }                 //
  41. int  Reset(int N,int cur){ return N = N & ~(1<<cur); }              //
  42. bool Check(int N,int cur){ return (bool)(N & (1<<cur)); }           //
  43. LL   GCD(LL a,LL b){ if(b == 0) return a; return GCD(b,a%b);}       //
  44. LL   LCM(LL a,LL b){ return a*b/GCD(a,b);}                          //
  45. LL   POW(LL a,LL p){ LL res = 1,x = a;while(p){if(p&1)              //
  46.      res = (res*x); x = (x*x);p >>= 1;} return res;}                //
  47. //==================================================================//
  48.  
  49. //==================================================================//
  50. //int knightDir[8][2] = {{-2,1},{-1,2},{1,2},{2,1},                 //
  51. //                      {2,-1},{-1,-2},{1,-2},{-2,-1}};             //
  52. //int dir8[4][2]      = {{-1,0},{0,1},{1,0},{0,-1},                 //
  53. //                      {-1,-1},{1,1},{1,-1},{-1,1}};               //
  54. //int dir4[4][2]      = {{-1,0},{0,1},{1,0},{0,-1}};                //
  55. //==================================================================//
  56. //=======// Done With The Shortcut Stuffs! Now Let's Code! //=======//
  57.  
  58. #define Mod 1000000007
  59.  
  60. struct edge{
  61.     int v;
  62.     int idx;
  63.     edge(int a,int b){
  64.         v = a;
  65.         idx = b;
  66.     }
  67. };
  68.  
  69. int N,M,u,v;
  70. vector<edge> Graph[100005];
  71. int ind1[100005];
  72. int ind2[100005];
  73.  
  74. pair<int,int> E[100005];
  75.  
  76. bool isDist(){
  77.     queue<int> Q;
  78.     for(int i = 1;i<=N;i++){
  79.         ind1[i] = ind2[i];
  80.         if(ind1[i] == 0) Q.push(i);
  81.     }
  82.     while(Q.empty() == false){
  83.         if(Q.size() > 1) return false;
  84.         int u = Q.front();
  85.         Q.pop();
  86.         int Sz = Graph[u].size();
  87.         for(int i = 0;i<Sz;i++){
  88.             int v = Graph[u][i].v;
  89.             ind1[v]--;
  90.             if(ind1[v] == 0){
  91.                 Q.push(v);
  92.             }
  93.         }
  94.     }
  95.     return true;
  96. }
  97.  
  98. bool isValid(int k){
  99.     queue<int> Q;
  100.     mems(ind1,0);
  101.     for(int i = 1;i<=N;i++){
  102.         Graph[i].clear();
  103.     }
  104.     for(int i = 1;i<=k;i++){
  105.         int u = E[i].first;
  106.         int v = E[i].second;
  107.         Graph[u].pb(edge(v,i));
  108.         ind1[v]++;
  109.     }
  110.     for(int i = 1;i<=N;i++){
  111.         if(ind1[i] == 0) Q.push(i);
  112.     }
  113.     while(Q.empty() == false){
  114.         if(Q.size() > 1) return false;
  115.         int u = Q.front();
  116.         Q.pop();
  117.         int Sz = Graph[u].size();
  118.         for(int i = 0;i<Sz;i++){
  119.             int v = Graph[u][i].v;
  120.             ind1[v]--;
  121.             if(ind1[v] == 0){
  122.                 Q.push(v);
  123.             }
  124.         }
  125.     }
  126.     return true;
  127. }
  128.  
  129. int solve(){
  130.     int L = 1,R = M;
  131.     while(L<R){
  132.         int mid = (L+R)/2;
  133.         bool rs = isValid(L);
  134.         if(rs == true){
  135.             R = mid-1;
  136.         }else{
  137.             L = mid+1;
  138.         }
  139.     }
  140.     if(L>1) L--;if(L>1) L--;
  141.     while(L<M){
  142.         bool rs = isValid(L);
  143.         if(rs == true) break;
  144.         L++;
  145.     }
  146.     if(L>M) L = M;
  147.     return L;
  148. }
  149.  
  150. int main(){
  151.     sf("%d %d",&N,&M);
  152.     mems(ind1,0);
  153.     for(int i = 1;i<=M;i++){
  154.         sf("%d %d",&u,&v);
  155.         E[i] = mp(u,v);
  156.         Graph[u].pb(edge(v,i));
  157.         ind1[v]++;
  158.         ind2[v]++;
  159.     }
  160.     bool f = isDist();
  161.     if(f == false){
  162.         cout << "-1" << endl;
  163.         return 0;
  164.     }
  165.     int res = solve();
  166.     cout << res << endl;
  167. }
RAW Paste Data