SHARE
TWEET

Untitled

a guest May 6th, 2019 129 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define rep(i,n) for(int i = 0; i < (n); ++i)
  5. #define rrep(i,n) for(int i = 1; i <= (n); ++i)
  6. #define drep(i,n) for(int i = (n)-1; i >= 0; --i)
  7. #define srep(i,s,t) for (int i = s; i < t; ++i)
  8. #define rng(a) a.begin(),a.end()
  9. #define rrng(a) a.rbegin(),a.rend()
  10. #define maxs(x,y) (x = max(x,y))
  11. #define mins(x,y) (x = min(x,y))
  12. #define limit(x,l,r) max(l,min(x,r))
  13. #define lims(x,l,r) (x = max(l,min(x,r)))
  14. #define isin(x,l,r) ((l) <= (x) && (x) < (r))
  15. #define pb push_back
  16. #define sz(x) (int)(x).size()
  17. #define pcnt __builtin_popcountll
  18. #define uni(x) x.erase(unique(rng(x)),x.end())
  19. #define snuke srand((unsigned)clock()+(unsigned)time(NULL));
  20. #define show(x) cout<<#x<<" = "<<x<<endl;
  21. #define PQ(T) priority_queue<T,v(T),greater<T> >
  22. #define bn(x) ((1<<x)-1)
  23. #define dup(x,y) (((x)+(y)-1)/(y))
  24. #define newline puts("")
  25. #define v(T) vector<T>
  26. #define vv(T) v(v(T))
  27. using namespace std;
  28. typedef long long int ll;
  29. typedef unsigned uint;
  30. typedef unsigned long long ull;
  31. typedef pair<int,int> P;
  32. typedef vector<int> vi;
  33. typedef vector<vi> vvi;
  34. typedef vector<ll> vl;
  35. typedef vector<P> vp;
  36. inline int in() { int x; scanf("%d",&x); return x;}
  37. template<typename T>inline istream& operator>>(istream&i,v(T)&v)
  38. {rep(j,sz(v))i>>v[j];return i;}
  39. template<typename T>string join(const v(T)&v)
  40. {stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
  41. template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
  42. {if(sz(v))o<<join(v);return o;}
  43. template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
  44. {return i>>v.fi>>v.se;}
  45. template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
  46. {return o<<v.fi<<","<<v.se;}
  47. template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
  48. const double eps = 1e-10;
  49. const ll LINF = 1001002003004005006ll;
  50. const int INF = 1001001001;
  51. #define dame { puts("-1"); return 0;}
  52. #define yn {puts("YES");}else{puts("NO");}
  53. const int MX = 200005;
  54.  
  55. // Max flow
  56. // !! Be care of double and INF !!
  57. struct Maxflow {
  58.   typedef int TT;
  59.   int n;
  60.   vi to, next, head, dist, it;
  61.   vector<TT> lim;
  62.   Maxflow(){}
  63.   Maxflow(int n):n(n),head(n,-1),it(n){}
  64.   void add(int a, int b, TT c=1) {
  65.     next.pb(head[a]); head[a] = sz(to); to.pb(b); lim.pb(c);
  66.     next.pb(head[b]); head[b] = sz(to); to.pb(a); lim.pb(0);
  67.   }
  68.   // void add2(int a, int b, int c=1) {
  69.   //   next.pb(head[a]); head[a] = sz(to); to.pb(b); lim.pb(c);
  70.   //   next.pb(head[b]); head[b] = sz(to); to.pb(a); lim.pb(c);
  71.   // }
  72.   void bfs(int sv) {
  73.     dist = vi(n,INF);
  74.     queue<int> q;
  75.     dist[sv] = 0; q.push(sv);
  76.     while (!q.empty()){
  77.       int v = q.front(); q.pop();
  78.       for (int i = head[v]; i != -1; i = next[i]) {
  79.         if (lim[i] && dist[to[i]] == INF) { // double INF !!
  80.           dist[to[i]] = dist[v]+1; q.push(to[i]);
  81.         }
  82.       }
  83.     }
  84.   }
  85.   TT dfs(int v, int tv, TT nf=INF) { // INF !!
  86.     if (v == tv) return nf;
  87.     for (; it[v] != -1; it[v] = next[it[v]]) {
  88.       int u = to[it[v]]; TT f;
  89.       if (!lim[it[v]] || dist[v] >= dist[u]) continue;
  90.       if (f = dfs(u, tv, min(nf, lim[it[v]])), f) { // double !!
  91.         lim[it[v]] -= f;
  92.         lim[it[v]^1] += f;
  93.         return f;
  94.       }
  95.     }
  96.     return 0;
  97.   }
  98.   TT solve(int sv, int tv) {
  99.     TT flow = 0, f;
  100.     while (1) {
  101.       bfs(sv);
  102.       if (dist[tv] == INF) return flow;
  103.       rep(i,n) it[i] = head[i];
  104.       while (f = dfs(sv,tv), f) flow += f;
  105.     }
  106.   }
  107. };
  108. //
  109.  
  110. int n;
  111. vvi to;
  112. vi ans;
  113. map<P,int> mp;
  114. int dfs(int v) {
  115.   int r = v<n?n-1:-n;
  116.   for (int u : to[v]) {
  117.     int x = dfs(u);
  118.     // cerr<<v<<" "<<u<<" "<<x<<endl;
  119.     if (v < n) ans[mp[P(v,u-n)]] = abs(x);
  120.     else ans[mp[P(u,v-n)]] = abs(x);
  121.     r += x;
  122.   }
  123.   return r;
  124. }
  125.  
  126. int main() {
  127.   int m;
  128.   scanf("%d%d",&n,&m);
  129.  
  130.   int sv = n+(n-1), tv = sv+1;
  131.   Maxflow g(tv+1);
  132.   vp es;
  133.   vvi ato(n);
  134.   rep(i,m) {
  135.     int a,b;
  136.     scanf("%d%d",&a,&b);
  137.     --a; --b;
  138.     swap(a,b);
  139.     es.pb(P(a,b));
  140.     mp[P(a,b)] = i;
  141.     g.add(a,n+b);
  142.     ato[a].pb(b);
  143.   }
  144.   rep(i,n) g.add(sv,i);
  145.   rep(i,n-1) g.add(n+i,tv);
  146.   if (g.solve(sv,tv) != n-1) dame;
  147.   to = vvi(sv);
  148.   vi p(n-1);
  149.   vi pp(n,-1);
  150.   rep(i,m) {
  151.     int e = i<<1;
  152.     if (!g.lim[e]) {
  153.       int a = es[i].fi, b = es[i].se;
  154.       to[n+b].pb(a);
  155.       p[b] = a;
  156.       pp[a] = b;
  157.     }
  158.   }
  159.   int root = -1;
  160.   rep(i,n) if (pp[i] == -1) root = i;
  161.   vi p2(n-1,-1);
  162.   {
  163.     queue<int> q;
  164.     for (int b : ato[root]) {
  165.       if (p2[b] != -1) continue;
  166.       p2[b] = root;
  167.       q.push(b);
  168.     }
  169.     while (sz(q)) {
  170.       int v = q.front(); q.pop();
  171.       v = p[v];
  172.       for (int b : ato[v]) {
  173.         if (p2[b] != -1) continue;
  174.         p2[b] = v;
  175.         q.push(b);
  176.       }
  177.     }
  178.     rep(i,n-1) {
  179.       if (p2[i] == -1) dame;
  180.       to[p2[i]].pb(n+i);
  181.     }
  182.   }
  183.   ans = vi(m);
  184.   dfs(root);
  185.   for (int x : ans) printf("%d\n",x);
  186.   return 0;
  187. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top