fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. /* Merge 2 vector thanh 1
  5.  merge(Tree[2 * id].begin(), Tree[2 * id].end(),
  6.               Tree[2 * id + 1].begin(), Tree[2 * id + 1].end(),
  7.               back_inserter(Tree[id]));
  8. */
  9.  
  10. /*legendry
  11. int legendry(int n, int p)
  12. {
  13.     int ans = 0, x = 1;
  14.     while (x * p <= n)
  15.     {
  16.         x *= p;
  17.         ans += n/x;
  18.     }
  19.     return ans;
  20. }
  21. */
  22.  
  23. /* Phi ham euler
  24. int Phi(int x)
  25. {
  26.     int res = 0;
  27.     for (int i = 2; i <= sqrt(x); i++)
  28.     {
  29.         if (x % i == 0)
  30.         {
  31.             res -= res / i;
  32.             while (x % i == 0)
  33.             {
  34.                 x /= i;
  35.             }
  36.         }
  37.     }
  38.     if (x > 1) res -= res / x;
  39.     return res;
  40. }
  41.  
  42. int phi[N];
  43.  
  44. void sang(int x)
  45. {
  46.     fu(i, 1, x) phi[i] = i;
  47.  
  48.     fu(i, 2, x)
  49.     {
  50.         if (phi[i] == i)
  51.         {
  52.             for (int j = i; j <= x; j += i)
  53.             {
  54.                 phi[j] -= phi[j] / i;
  55.             }
  56.         }
  57.     }
  58. }
  59. */
  60.  
  61. /* To Hop
  62. const int MAX = 2e5 + 1;
  63.  
  64. int powmod(int a, int b)
  65. {
  66.     if (b == 0) return 1;
  67.     else if (b == 1) return a % MOD;
  68.     int vl = powmod(a, b/2);
  69.     if (b % 2 == 0) return vl * vl % MOD;
  70.     return 1ll * (vl * vl % MOD) * (a % MOD) % MOD;
  71. }
  72.  
  73. void preComb()
  74. {
  75.     frac[0] = 1;
  76.     fu(i,1,MAX) frac[i] = 1LL * frac[i - 1] * i % MOD;
  77.     finv[MAX] = powmod(frac[MAX], MOD - 2);
  78.     fd(i,MAX,1) finv[i - 1] = 1LL * finv[i] * i % MOD;
  79. }
  80.  
  81. int Comb(int k, int n)
  82. {
  83.     return k > n ? 0 : 1LL * frac[n] * finv[k] % MOD * finv[n - k] % MOD;
  84. }
  85. */
  86.  
  87. /* Fenwick 2d
  88. struct Fenwick2D
  89. {
  90.     vector<vector<int>> Tree;
  91.     int m, n;
  92.     Fenwick2D(int _m = 0, int _n = 0)
  93.     {
  94.         m = _m;
  95.         n = _n;
  96.         Tree.resize(m + 1);
  97.         fu(i,0,m)
  98.         {
  99.             Tree[i].resize(n + 1);
  100.             fill(Tree[i].begin(), Tree[i].end(), 0);
  101.         }
  102.     }
  103.     void update(int x, int y, int vl)
  104.     {
  105.         for(int i = x; i <= m; i += i&-i)
  106.         {
  107.             for(int j = y; j <= n; j += j&-j)
  108.             {
  109.                 Tree[i][j] += vl;
  110.             }
  111.         }
  112.     }
  113.     int get(int x, int y)
  114.     {
  115.         int res = 0;
  116.         for(int i = x; i > 0; i -= i&-i)
  117.         {
  118.             for(int j = y; j > 0; j -= j&-j)
  119.             {
  120.                 res += Tree[i][j];
  121.             }
  122.         }
  123.         return res;
  124.     }
  125. } F2D;
  126. */
  127. /* HLD
  128.  void dfs(int u, int p)
  129.  {
  130.      child[u] = 1;
  131.      for (int v : adj[u]) if (v != p)
  132.      {
  133.          par[v] = u;
  134.          depth[v] = depth[u] + 1;
  135.          dfs(v, u);
  136.          child[u] += child[v];
  137.      }
  138.  }
  139.  
  140.  int lca(int u, int v)
  141.  {
  142.     while(ChainId[u] != ChainId[v])
  143.     {
  144.         if(ChainId[u] > ChainId[v])
  145.         {
  146.             u = par[head[ChainId[u]]];
  147.         }
  148.         else
  149.         {
  150.             v = par[head[ChainId[v]]];
  151.         }
  152.     }
  153.     if(depth[u] < depth[v]) return u;
  154.     return v;
  155. }
  156.  
  157. void hld(int u, int p)
  158.  {
  159.      if (!head[CurChain]) head[CurChain] = u;
  160.      ChainId[u] = CurChain;
  161.      Pos[u] = ++CurPos;
  162.      Arr[CurPos] = v[u];
  163.      int MaxNode = 0;
  164.      for(int v : adj[u]) if (v != p)
  165.      {
  166.          if (child[v] > child[MaxNode]) MaxNode = v;
  167.      }
  168.      if (MaxNode) hld(MaxNode, u);
  169.      for(int v : adj[u]) if (v != p && v != MaxNode)
  170.      {
  171.          CurChain++;
  172.          hld(v, u);
  173.      }
  174.  }
  175.  
  176.  int Query(int u, int v)
  177. {
  178.     int Lca = lca(u, v);
  179.     int ans = LLONG_MIN;
  180.     while (ChainId[u] != ChainId[Lca])
  181.     {
  182.         maximize(ans, S.query(1,1,CurPos,Pos[head[ChainId[u]]], Pos[u]));
  183.         u = par[head[ChainId[u]]];
  184.     }
  185.     while (ChainId[v] != ChainId[Lca])
  186.     {
  187.         maximize(ans, S.query(1,1,CurPos,Pos[head[ChainId[v]]], Pos[v]));
  188.         v = par[head[ChainId[v]]];
  189.     }
  190.     if (depth[u] < depth[v])
  191.     {
  192.         maximize(ans, S.query(1,1,CurPos,Pos[u],Pos[v]));
  193.     }else maximize(ans, S.query(1,1,CurPos,Pos[v],Pos[u]));
  194.     return ans;
  195. }
  196. */
  197.  
  198. /*
  199. Convex Hull Trick Min
  200. int pointer;
  201. vector<ll> M;
  202. vector<ll> B;
  203.  
  204. bool bad(int l1,int l2,int l3)
  205. {
  206. 	return (B[l3] - B[l1]) * (M[l1] - M[l2]) < (B[l2] - B[l1]) * (M[l1] - M[l3]);
  207. }
  208.  
  209. void add(ll m,ll b)
  210. {
  211. 	M.push_back(m);
  212. 	B.push_back(b);
  213. 	while (M.size() >= 3 && bad(M.size() - 3, M.size() - 2, M.size() - 1))
  214. 	{
  215. 		M.erase(M.end()-2);
  216. 		B.erase(B.end()-2);
  217. 	}
  218. }
  219.  
  220. ll query(ll x)
  221. {
  222. 	if (pointer >= M.size())
  223.         pointer = M.size() - 1;
  224. 	while (pointer < M.size() - 1 && M[pointer+1] * x + B[pointer+1] < M[pointer] * x + B[pointer])
  225. 		pointer++;
  226. 	return M[pointer] * x + B[pointer];
  227. }
  228. */
  229.  
  230. /* TRIE
  231. struct Trie
  232. {
  233.     struct Node
  234.     {
  235.         bool isEnd;
  236.         Node *child[26];
  237.         Node()
  238.         {
  239.             fu(i,0,25) child[i] = nullptr;
  240.             isEnd = 0;
  241.         }
  242.     };
  243.     Node *root = new Node();
  244.     void add(string str)
  245.     {
  246.         Node *x = root;
  247.         fu(i,0,str.size()-1)
  248.         {
  249.             int c = str[i] - 'a';
  250.             if (x->child[c] == nullptr) x->child[c] = new Node();
  251.             x = x->child[c];
  252.         }
  253.         x->isEnd = 1;
  254.     }
  255.     bool query(string str)
  256.     {
  257.         Node *x = root;
  258.         fu(i,0,str.size()-1)
  259.         {
  260.             int c = str[i] - 'a';
  261.             if (x->child[c] == nullptr) return false;
  262.             else x = x->child[c];
  263.         }
  264.         return (x->isEnd == 1);
  265.     }
  266. } T;
  267. */
  268.  
  269. /* KMP
  270. int kmp[N], match[N];
  271.  
  272. void cre_kmp()
  273. {
  274.     int k = kmp[1] = 0;
  275.     fu(i,2,m)
  276.     {
  277.         while (k > 0 && B[i] != B[k+1]) k = kmp[k];
  278.         kmp[i] = B[i] == B[k+1] ? ++k : 0;
  279.     }
  280. }
  281.  
  282. void cre_match()
  283. {
  284.     int k = 0;
  285.     fu(i,1,n)
  286.     {
  287.         while(k > 0 && A[i] != B[k+1]) k = kmp[k];
  288.         match[i] = A[i] == B[k+1] ? ++k : 0;
  289.         if (match[i] == m) cout<<i - m + 1<<sp;
  290.     }
  291. }
  292. */
  293.  
  294. /* CHIA CAN
  295.    fu(i,1,q)
  296.     {
  297.         int t; cin>>t;
  298.         if (t == 1)
  299.         {
  300.             int u, v; cin>>u>>v;
  301.             auto it = blck[u/sq].lower_bound(a[u]);
  302.             blck[u/sq].erase(it);
  303.             a[u] = v;
  304.             blck[u/sq].insert(a[u]);
  305.         }
  306.         else
  307.         {
  308.             int L, R, k; cin>>L>>R>>k;
  309.             int res = INT_MAX;
  310.             int blockL = (L - 1) / sq + 1;
  311.             int blockR = R / sq - 1;
  312.  
  313.             fu(i,blockL,blockR)
  314.             {
  315.                 auto it = blck[i].lower_bound(k);
  316.                 if (it != blck[i].end()) minimize(res, *it);
  317.             }
  318.  
  319.             if (L/sq != R/sq)
  320.             {
  321.                 fu(i,L,blockL*sq-1) if (a[i] >= k) minimize(res, a[i]);
  322.                 fu(i,(blockR+1)*sq,R) if (a[i] >= k) minimize(res, a[i]);
  323.             }
  324.             else fu(i,L,R) if (a[i] >= k) minimize(res, a[i]);
  325.             cout<<(res == INT_MAX ? -1 : res)<<el;
  326.         }
  327.     }
  328.     */
  329.  
  330. /* DIJSKTRA
  331. void dijkstra(int st)
  332. {
  333.     d[st] = 0;
  334.     priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
  335.     q.push({0,st});
  336.     while (!q.empty())
  337.     {
  338.         pair<l, int> tmp = q.top();
  339.         q.pop();
  340.         int u = tmp.second;
  341.         int w = tmp.first;
  342.         if (w > d[u]) continue;
  343.         for (auto it : adj[u])
  344.         {
  345.             int v = it.first;
  346.             int c = it.second;
  347.             if (maximize(d[v], w + c))
  348.             {
  349.                 q.push({d[v], v});
  350.             }
  351.         }
  352.     }
  353. }
  354.  
  355. /* FENWICK TREE
  356. struct Fenwick
  357. {
  358.     vector<pair<ll, int>> Tree;
  359.     int n;
  360.     Fenwick(int _n = 0)
  361.     {
  362.         n = _n;
  363.         Tree.resize(n+1);
  364.     }
  365.     void update(ll x, ll vl)
  366.     {
  367.         for(;x<=n;x+=x&-x)
  368.         {
  369.             Tree[x].first+=vl;
  370.             Tree[x].second++;
  371.         }
  372.     }
  373.     pair<ll,int> get(ll x)
  374.     {
  375.         pair<ll, int> tmp;
  376.         for(;x;x-=x&-x)
  377.         {
  378.             tmp.first += Tree[x].first;
  379.             tmp.second += Tree[x].second;
  380.         }
  381.         return tmp;
  382.     }
  383.     pair<ll,int> query(int l, int r)
  384.     {
  385.         if (l == 0) return get(r);
  386.         return {get(r).first - get(l-1).first, get(r).se - get(l-1).se};
  387.     }
  388. } F;
  389.  
  390. /* SEGMENT TREE
  391. struct Segment
  392. {
  393.     struct Node
  394.     {
  395.         ll vl, lz;
  396.         Node(ll _vl = 0, ll _lz = 0)
  397.         {
  398.             vl = _vl;
  399.             lz = _lz;
  400.         }
  401.     };
  402.     vector<Node> Tree;
  403.     int n;
  404.     Segment(int _n = 0)
  405.     {
  406.         n = _n;
  407.         Tree.resize(4*n+1);
  408.     }
  409.     void build(int id, int l, int r)
  410.     {
  411.         if (l == r)
  412.         {
  413.             Tree[id].vl = a[l];
  414.         }else
  415.         {
  416.             int m = (l + r)/2;
  417.             build(id*2, l, m);
  418.             build(id*2+1, m+1, r);
  419.             Tree[id].vl = max(Tree[id*2].vl, Tree[id*2+1].vl);
  420.         }
  421.     }
  422.     void down(int id)
  423.     {
  424.         Node &P = Tree[id], &L = Tree[id*2], &R = Tree[id*2+1];
  425.         if (P.lz)
  426.         {
  427.             L.vl += P.lz;
  428.             R.vl += P.lz;
  429.             L.lz += P.lz;
  430.             R.lz += P.lz;
  431.             P.lz = 0;
  432.         }
  433.     }
  434.     void update(int id, int l, int r, int u, int v, ll vl)
  435.     {
  436.         if (l > v || r < u) return;
  437.         if (l >= u && r <= v)
  438.         {
  439.             Tree[id].vl += vl;
  440.             Tree[id].lz += vl;
  441.             return;
  442.         }
  443.         down(id);
  444.         int m = (l + r)/2;
  445.         update(id*2, l, m, u, v, vl);
  446.         update(id*2+1, m+1, r, u, v, vl);
  447.         Tree[id].vl = max(Tree[id*2].vl, Tree[id*2+1].vl);
  448.     }
  449.     ll query(int id, int l, int r, int u, int v)
  450.     {
  451.         if (l > v || r < u) return INT_MIN;
  452.         if (l >= u && r <= v) return Tree[id].vl;
  453.         down(id);
  454.         int m = (l+r)/2;
  455.         int L = query(id*2, l, m, u, v);
  456.         int R = query(id*2+1, m+1, r, u, v);
  457.         return max(L, R);
  458.     }
  459. } S;
  460. /*
  461.  
  462. /* DSU
  463. struct DSU
  464. {
  465.     vector<ll> lab;
  466.     int n;
  467.     DSU(int _n = 0)
  468.     {
  469.         n = _n;
  470.         lab.resize(n + 1);
  471.         fill(lab.begin(), lab.end(), -1);
  472.     }
  473.     int Find(int u)
  474.     {
  475.         return lab[u] < 0 ? u : lab[u] = Find(lab[u]);
  476.     }
  477.     ll Union(int u, int v)
  478.     {
  479.         u = Find(u);
  480.         v = Find(v);
  481.         if (u == v) return 0;
  482.         ll res = 1ll * lab[u] * lab[v];
  483.         if (lab[u] > lab[v]) swap(u, v);
  484.         lab[u] += lab[v];
  485.         lab[v] = u;
  486.         return res;
  487.     }
  488. } D;
  489. */
  490.  
  491. /* NENSO
  492. void nenso()
  493. {
  494.     sort(vt.begin(), vt.end());
  495.     vt.resize(unique(vt.begin(), vt.end()) - vt.begin());
  496.     fu(i,1,n) a[i] = lower_bound(vt.begin(), vt.end(), a[i]) - vt.begin() + 1;
  497.     fu(i,1,q)
  498.     {
  499.         st[i].x = lower_bound(vt.begin(), vt.end(), st[i].x) - vt.begin() + 1;
  500.         if (st[i].tp == '?') st[i].k = lower_bound(vt.begin(), vt.end(), st[i].k) - vt.begin() + 1;
  501.     }
  502. }
  503. */
  504.  
  505. /* Kruskal
  506. bool cmp(Edge a, Edge b)
  507. {
  508.     return a.c < b.c;
  509. }
  510.  
  511. vector<Edge> mst;
  512.  
  513. void kruskal()
  514. {
  515.     sort(st + 1, st + m +1, cmp);
  516.     ll d = 0;
  517.     for (int i = 1; i <= m; i++)
  518.     {
  519.         if (mst.size() == n - 1) break;
  520.         if (Union(st[i].u, st[i].v))
  521.         {
  522.             mst.push_back(st[i]);
  523.             d += st[i].c;
  524.         }
  525.     }
  526. }
  527. */
  528.  
  529. /* SPARSE TABLE
  530.  
  531. int log2_floor(int n) { return 31 - __builtin_clz(n); }
  532.  
  533.  
  534. ll query_rmq(int l, int r)
  535. {
  536.     int i = log2_floor(r-l+1);
  537.     return min(table[i][l], table[i][r - MASK(i) + 1]);
  538. }
  539.  
  540. void pre
  541. {
  542.     fu(i,1,n) table[0][i] = a[i];
  543.  
  544.     fu(j,1,Log)
  545.     {
  546.         for (int i = 1; i + MASK(j) - 1 <= n; i++)
  547.         {
  548.             table[j][i] = min(table[j-1][i], table[j-1][i + MASK(j - 1)]);//rmq hay rsq thi thay doi min hoac s
  549.         }
  550.     }
  551. }
  552. */
  553.  
  554. /* KIEM TRA CHU TRINH
  555. 1. DO THI VO HUONG DUNG DSU
  556. 2. DO THI CO HUONG
  557. bool dfs(int u)
  558. {
  559.     col[u] = 1;
  560.     for (int v : adj[u])
  561.     {
  562.         if (col[v] == 0)
  563.         {
  564.             par[v] = u;
  565.             if (dfs(v)) return true;
  566.         }else if (col[v] == 1) return true;
  567.     }
  568.     col[u] = 2;
  569.     return false;
  570. }
  571. */
  572.  
  573. /*
  574. LCA
  575.  
  576. void dfs(int u, int p)
  577. {
  578.     for (int v : adj[u]) if (v != p)
  579.     {
  580.         high[v] = high[u] + 1;
  581.         par[v][0] = u;
  582.         dfs(v, u);
  583.     }
  584. }
  585.  
  586. void pre()
  587. {
  588.     dfs(1, -1);
  589.  
  590.     for (int j = 1; j <= Log; j++)
  591.     {
  592.         for (int i = 1; i <= n; i++)
  593.         {
  594.             par[i][j] = par[par[i][j-1]][j-1];
  595.         }
  596.     }
  597.     high[0] = -1;
  598. }
  599.  
  600. int lca(int u, int v)
  601. {
  602.     if (high[v] > high[u]) return lca(v, u);
  603.  
  604.     fd(i, Log, 0)
  605.     {
  606.         if(high[par[u][i]] >= high[v])
  607.             u = par[u][i];
  608.     }
  609.  
  610.     if (u == v) return u;
  611.  
  612.     fd(i, Log, 0)
  613.     {
  614.         if (par[u][i] != par[v][i])
  615.         {
  616.             u = par[u][i];
  617.             v = par[v][i];
  618.         }
  619.     }
  620.     return par[u][0];
  621. }
  622. */
  623.  
  624. /* ERAS DOAN
  625. void eras_doan()
  626. {
  627.     fu(i,2,(int)1e6)
  628.     {
  629.         ll j = (l + i - 1) /i *i;
  630.         for (;j<=r; j+=i) if (j != i)
  631.             d[j-l] = 1
  632.     }
  633.     for (int i = 0; i < r-l; i++) if (d[i]==0) cout<<i+l<<sp;
  634. }
  635. */
  636.  
  637. /* LUONG CUC DAI
  638. struct edge
  639. {
  640.     int x, y, cap, flow;
  641. };
  642.  
  643. struct Flow
  644. {
  645.     int n, S, T;
  646.     vector < vector <int> > a;
  647.     vector <int> cur, d;
  648.     vector <edge> e;
  649.  
  650.     Flow() {}
  651.     Flow(int _n, int _S, int _T)
  652.     {
  653.         n = _n; S = _S; T = _T;
  654.         a = vector < vector <int> >(n + 1);
  655.         cur = vector <int>(n + 1);
  656.         d = vector <int>(n + 1);
  657.     }
  658.  
  659.     void addEdge(int x, int y, int _cap)
  660.     {
  661.         edge e1 = {x, y, _cap, 0};
  662.         edge e2 = {y, x, 0, 0};
  663.         a[x].push_back(e.size()); e.push_back(e1);
  664.         a[y].push_back(e.size()); e.push_back(e2);
  665.     }
  666.  
  667.     int bfs()
  668.     {
  669.         queue<int> q;
  670.         for (int i = 1; i <= n; i++) d[i] = -1;
  671.         q.push(S); d[S] = 0;
  672.         while (!q.empty() && d[T] < 0)
  673.         {
  674.             int x = q.front(); q.pop();
  675.             for (int i = 0; i < (int)a[x].size(); i++)
  676.             {
  677.                 int id = a[x][i], y = e[id].y;
  678.                 if (d[y] < 0 && e[id].flow < e[id].cap)
  679.                     q.push(y), d[y] = d[x] + 1;
  680.             }
  681.         }
  682.         return d[T] >= 0;
  683.     }
  684.  
  685.     int dfs(int x, int val)
  686.     {
  687.         if (!val) return 0;
  688.         if (x == T) return val;
  689.         for (; cur[x] < (int)a[x].size(); cur[x]++)
  690.         {
  691.             int id = a[x][cur[x]], y = e[id].y;
  692.             if (d[y] != d[x] + 1) continue;
  693.             int pushed = dfs(y, min(val, e[id].cap - e[id].flow));
  694.             if (pushed)
  695.             {
  696.                 e[id].flow += pushed;
  697.                 e[id ^ 1].flow -= pushed;
  698.                 return pushed;
  699.             }
  700.         }
  701.         return 0;
  702.     }
  703.  
  704.     int maxFlow()
  705.     {
  706.         int res = 0;
  707.         while (bfs())
  708.         {
  709.             for (int i = 1; i <= n; i++) cur[i] = 0;
  710.             while (1)
  711.             {
  712.                 int val = dfs(S, oo);
  713.                 if (!val) break;
  714.                 res += val;
  715.             }
  716.         }
  717.         return res;
  718.     }
  719. };
  720. */
  721.  
  722. /* Matrix Multiplication
  723. const int MATRIX_SIZE = 20;
  724.  
  725. struct Matrix {
  726.     int m, n;
  727.     long long d[MATRIX_SIZE][MATRIX_SIZE];
  728.  
  729.     Matrix(int _m = 0, int _n = 0) {
  730.         m = _m; n = _n;
  731.         memset(d, 0, sizeof d);
  732.     }
  733.  
  734.     Matrix operator + (const Matrix &a) const {
  735.         Matrix res(m, n);
  736.         for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) {
  737.             res.d[i][j] = d[i][j] + a.d[i][j];
  738.             if (res.d[i][j] >= MOD) res.d[i][j] -= MOD;
  739.         }
  740.         return res;
  741.     }
  742.  
  743.     Matrix operator * (const Matrix &a) const {
  744.         int x = m, y = n, z = a.n;
  745.         Matrix res(x, z);
  746.         for (int i = 0; i < x; i++) for (int j = 0; j < y; j++)
  747. 		for (int k = 0; k < z; k++) {
  748.             	res.d[i][k] += 1LL * d[i][j] * a.d[j][k];
  749.             	if (res.d[i][k] >= 1LL * MOD * MOD) res.d[i][k] -= 1LL * MOD * MOD;
  750.         	}
  751.         for (int i = 0; i < x; i++) for (int k = 0; k < z; k++) res.d[i][k] %= MOD;
  752.  
  753.         return res;
  754.     }
  755.  
  756.     Matrix operator ^ (long long k) const {
  757.         Matrix res(n, n);
  758.         for (int i = 0; i < n; i++) res.d[i][i] = 1;
  759.         Matrix mul = *this;
  760.         while (k > 0) {
  761.             if (k & 1) res = res * mul;
  762.             mul = mul * mul;
  763.             k >>= 1;
  764.         }
  765.         return res;
  766.     }
  767.  
  768.     long long* operator[] (int i) {
  769.         return d[i];
  770.     }
  771.  
  772.     const long long* operator[] (int i) const {
  773.         return d[i];
  774.     }
  775. };
  776. */
  777.  
  778. /* CAP GHEP CUC DAI KHONG TRONG SO
  779. struct matcher {
  780.     const int oo = 100000000;
  781.     int m, n;
  782.     vector<int> mx, my, dist;
  783.     vector<vector<int>> ke;
  784.     int matched;
  785.  
  786.     matcher(int m, int n):
  787.         m(m), n(n),
  788.         mx(m+1, 0), my(n+1, 0), dist(m+1),
  789.         ke(m+1),
  790.         matched(0) {}
  791.  
  792.     void add_edge(int u, int v) {
  793.         ke[u].push_back(v);
  794.     }
  795.  
  796.     bool bfs() {
  797.         queue<int> Q;
  798.         for (int u=1; u<=m; u++) {
  799.             if (!mx[u]) {
  800.                 dist[u] = 0;
  801.                 Q.push(u);
  802.             } else {
  803.                 dist[u] = oo;
  804.             }
  805.         }
  806.  
  807.         bool found = false;
  808.         while (!Q.empty()) {
  809.             int u = Q.front(); Q.pop();
  810.             for (int v: ke[u]) {
  811.                 if (!my[v]) {
  812.                     found = true;
  813.                 } else if (dist[my[v]] == oo) {
  814.                     dist[my[v]] = dist[u] + 1;
  815.                     Q.push(my[v]);
  816.                 }
  817.             }
  818.         }
  819.  
  820.         return found;
  821.     }
  822.  
  823.     bool dfs(int u) {
  824.         if (dist[u] == oo) return false;
  825.         for (int v: ke[u]) {
  826.             if (!my[v] || (dist[my[v]]==dist[u]+1 && dfs(my[v]))) {
  827.                 mx[u] = v;
  828.                 my[v] = u;
  829.                 return true;
  830.             }
  831.         }
  832.         return false;
  833.     }
  834.  
  835.     void match() {
  836.         while(bfs()) {
  837.             for (int u=1; u<=m; u++) if (!mx[u]) matched += dfs(u);
  838.         }
  839.     }
  840. };
  841.  
  842. int get()
  843. {
  844.     matcher z(n, n);
  845.     fu(i,1,m)
  846.     {
  847.         int u, v; cin>>u>>v;
  848.         z.add_edge(u, v);
  849.     }
  850.     z.match();
  851.     return z.matched;
  852. }
  853. */
  854.  
  855. signed main()
  856. {
  857.  
  858. }
  859.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QQqbPA
language:
C++14 (gcc 8.3)
created:
41 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!