codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

687.md (21253B)


      1 Source: https://codeforces.com/blog/entry/45770
      2 
      3 Hi again!
      4 
      5 If you notice typos or errors, please send a private message.
      6 
      7 ### [688A: Opponents](//codeforces.com/contest/688/problem/A)
      8 
      9 #### Solution
     10 
     11 Let's find out for each row of the given matrix if it is completely consisting of *ones* or not. Make another array *canWin*, and set *canWin**i* equal to one if the *i*-th row consists at least one *zero*. Then the problem is to find the maximum subsegment of *canWin* array, consisting only ones. It can be solved by finding for each element of *canWin*, the closest zero to it from left. The complexity of this solution is *O*(*nd*), but the limits allow you to solve the problem in *O*(*nd*2) by iterating over all possible subsegments and check if each one of them is full of *ones* or not.
     12 
     13 **C++ code**
     14 
     15 ```
     16 	//     . .. ... .... ..... be name khoda ..... .... ... .. .     \\
     17 
     18 #include <bits/stdc++.h>
     19 using namespace std;
     20 
     21 inline int in() { int x; scanf("%d", &x); return x; }
     22 const int N = 202;
     23 
     24 int a[N][N];
     25 
     26 int main()
     27 {
     28 	int n = in(), d = in();
     29 	int ans = 0, cur = 0;
     30 	for(int i = 0; i < d; i++)
     31 	{
     32 		string s;
     33 		cin >> s;
     34 		bool iff = 0;
     35 		for(int j = 0; j < n; j++)
     36 			iff |= (s[j] == '0');
     37 		if(iff)
     38 			cur++;
     39 		else
     40 			cur = 0;
     41 		ans = max(ans, cur);
     42 	}
     43 	cout << ans << endl;
     44 }
     45 ```
     46 
     47 **Python code**
     48 
     49 ```
     50 n, d = map(int, raw_input().split())
     51 cur = 0
     52 ans = 0
     53 for i in range(d):
     54     s = raw_input()
     55     if (s == '1' * n):
     56         cur = 0
     57     else:
     58         cur += 1
     59     ans = max(ans, cur)
     60 print ans
     61 ```
     62 
     63 ### [688B: Lovely Palindromes](//codeforces.com/contest/688/problem/B)
     64 
     65 #### Hint
     66 
     67 Try to characterize even-length palindrome numbers.
     68 
     69 #### Solution
     70 
     71 For simplifications, in the following solution we define *lovely integer* as an even-length positive palindrome number.
     72 
     73 An even-length positive integer is lovely if and only if the first half of its digits is equal to the reverse of the second half.
     74 
     75 So if *a* and *b* are two different 2*k*-digit lovely numbers, then the first *k* digits of *a* and *b* differ in at least one position.
     76 
     77 So *a* is smaller than *b* if and only if the first half of *a* is smaller than the the first half of *b*.
     78 
     79 Another useful fact: The first half of a a lovely number can be any arbitrary positive integer.
     80 
     81 Using the above facts, it's easy to find the first half of the *n*-th lovely number — it exactly equals to integer *n*. When we know the first half of a lovely number, we can concatenate it with its reverse to restore the lovely integer. To sum up, the answer can be made by concatenating *n* and it's reverse together.
     82 
     83 The complexity of this solution is ![](https://espresso.codeforces.com/9040a33098f83986b0de64475c66584fbfdf0e22.png).
     84 
     85 **C++ code**
     86 
     87 ```
     88 	//     . .. ... .... ..... be name khoda ..... .... ... .. .     \\
     89 
     90 #include <bits/stdc++.h>
     91 using namespace std;
     92 
     93 inline int in() { int x; scanf("%d", &x); return x; }
     94 const long long N = 2002;
     95 
     96 int main()
     97 {
     98 	string s;
     99 	cin >> s;
    100 	cout << s;
    101 	reverse(s.begin(), s.end());
    102 	cout << s << endl;
    103 }
    104 ```
    105 
    106 **Python code**
    107 
    108 ```
    109 s = raw_input()
    110 print s + ''.join(reversed(s))
    111 ```
    112 
    113 #### Challenge
    114 
    115 What if you were asked to find *n*-th positive palindrome number? (1 ≤ *n* ≤ 1018)
    116 
    117 ### [687A: NP-Hard Problem](//codeforces.com/contest/687/problem/A)
    118 
    119 #### Hint
    120 
    121 Try to use all of the vertices. Then look at the two vertex covers together in the graph and see how it looks like.
    122 
    123 #### Solution
    124 
    125 Looking at the two vertex covers in the graph, you see there must be no edge *uv* that *u* and *v* are in the same vertex cover. So the two vertex covers form a bipartition of the graph, so the graph have to be bipartite. And being bipartite is also sufficient, you can use each part as a vertex cover. Bipartition can be found using your favorite graph traversing algorithm(BFS or DFS). [Here](http://stackoverflow.com/questions/30486784/how-to-find-if-a-graph-is-bipartite) is a tutorial for bipartition of undirected graphs.
    126 
    127 The complexity is *O*(*n* + *m*).
    128 
    129 **C++ code**
    130 
    131 ```
    132 	//     . .. ... .... ..... be name khoda ..... .... ... .. .     \\
    133 
    134 #include <bits/stdc++.h>
    135 using namespace std;
    136 
    137 inline int in() { int x; scanf("%d", &x); return x; }
    138 const int N = 120021;
    139 
    140 vector <int> vc[2];
    141 vector <int> g[N];
    142 int mark[N];
    143 
    144 bool dfs(int v, int color = 2)
    145 {
    146 	mark[v] = color;
    147 	vc[color - 1].push_back(v);
    148 	for(int u : g[v])
    149 	{
    150 		if(!mark[u] && dfs(u, 3 - color))
    151 				return 1;
    152 		if(mark[u] != 3 - color)
    153 			return 1;
    154 	}
    155 	return 0;
    156 }
    157 
    158 int main()
    159 {
    160 	int n, m;
    161 	cin >> n >> m;
    162 	for(int i = 0; i < m; i++)
    163 	{
    164 		int u = in() - 1;
    165 		int v = in() - 1;
    166 		g[u].push_back(v);
    167 		g[v].push_back(u);
    168 	}
    169 	for(int i = 0; i < n; i++)
    170 		if(!mark[i])
    171 		{
    172 		     if(g[i].empty())
    173 		          continue;
    174 		     if(dfs(i))
    175 			{
    176 				cout << -1 << endl;
    177 				return 0;
    178 			}
    179 		}
    180 	for(int i = 0; i < 2; i++)
    181 	{
    182 		cout << vc[i].size() << endl;
    183 		for(int v : vc[i])
    184 			cout << v + 1 << " ";
    185 		cout << endl;
    186 	}
    187 }
    188 ```
    189 
    190 #### Challenge
    191 
    192 In the same constraints, what if you were asked to give two disjoint edge covers from the given graph? (The edge covers must be edges-disjoint but they can have common vertex.)
    193 
    194 ### [687B: Remainders Game](//codeforces.com/contest/687/problem/B)
    195 
    196 #### Hint
    197 
    198 Assume the answer of a test is *No*. There must exist a pair of integers *x*1 and *x*2 such that both of them have the same remainders after dividing by any *c**i*, but they differ in remainders after dividing by *k*. Find more facts about *x*1 and *x*2!
    199 
    200 #### Solution
    201 
    202 Consider the *x*1 and *x*2 from the hint part. We have *x*1 - *x*2 ≡ 0 (![](https://espresso.codeforces.com/e5fe09004e6041073211aeaf5252a4fda6179ae5.png)) for each 1 ≤ *i* ≤ *n*.
    203 
    204 So:
    205 
    206 ![](https://espresso.codeforces.com/ce1aa6253ea02b48658a58e262d81556397a0d87.png)
    207 
    208 We also have ![](https://espresso.codeforces.com/6805af6ef595626ee44bca4f428f599a16c7a873.png) (![](https://espresso.codeforces.com/7ae14134424e2bb69d09c5d4f493f4bc361e274e.png)). As a result:
    209 
    210 ![](https://espresso.codeforces.com/f32add0af4a68edecbe23dfdb124ed23ddff95fb.png)
    211 
    212 We've found a necessary condition. And I have to tell you it's also sufficient!
    213 
    214 Assume ![](https://espresso.codeforces.com/f32add0af4a68edecbe23dfdb124ed23ddff95fb.png), we are going to prove there exists *x*1, *x*2 such that *x*1 - *x*2 ≡ 0 (![](https://espresso.codeforces.com/e5fe09004e6041073211aeaf5252a4fda6179ae5.png)) (for each 1 ≤ *i* ≤ *n*), and ![](https://espresso.codeforces.com/6805af6ef595626ee44bca4f428f599a16c7a873.png) (![](https://espresso.codeforces.com/7ae14134424e2bb69d09c5d4f493f4bc361e274e.png)).
    215 
    216 A possible solution is *x*1 = *lcm*(*c*1, *c*2, ..., *c**n*) and *x*2 = 2 × *lcm*(*c*1, *c*2, ..., *c**n*), so the sufficiency is also proved.
    217 
    218 So you have to check if *lcm*(*c*1, *c*2, ..., *c**n*) is divisible by *k*, which could be done using prime factorization of *k* and *c**i* values.
    219 
    220 For each integer *x* smaller than *MAXC*, find it's greatest prime divisor *gpd**x* using [sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) in ![](https://espresso.codeforces.com/7b352654ea7560e8c03f903a0fc31869c654af4e.png).
    221 
    222 Then using *gpd* array, you can write the value of each coin as *p*1*q*1*p*2*q*2...*p**m**q**m* where *p**i* is a prime integer and 1 ≤ *q**i* holds. This could be done in ![](https://espresso.codeforces.com/b23d8151f1dd3732717ef28bf702a24c690a7da9.png) by moving from *c**i* to ![](https://espresso.codeforces.com/a2b7dbfd17d1c0048a7b85d0c0190b2955ac932f.png) and adding *gpd**c**i* to the answer. And you can factorize *k* by the same way. Now for every prime *p* that ![](https://espresso.codeforces.com/77a51c559aa507abc405fe1aacba9e5bfa85133c.png), see if there exists any coin *i* that the power of *p* in the factorization of *c**i* is not smaller than the power of *p* in the factorization of *k*.
    223 
    224 Complexity is ![](https://espresso.codeforces.com/3d550743864f61bd57b21cd4528b29401b92499c.png).
    225 
    226 **C++ code**
    227 
    228 ```
    229 	//     . .. ... .... ..... be name khoda ..... .... ... .. .     \\
    230 
    231 #include <bits/stdc++.h>
    232 using namespace std;
    233 
    234 inline int in() { int x; scanf("%d", &x); return x; }
    235 const long long N = 1200021;
    236 
    237 int cntP[N], isP[N];
    238 
    239 int main()
    240 {
    241 	for(int i = 2; i < N; i++)
    242 		if(!isP[i])
    243 			for(int j = i; j < N; j += i)
    244 				isP[j] = i;
    245 	int n = in(), k = in();
    246 	for(int i = 0; i < n; i++)
    247 	{
    248 		int x = in();
    249 		while(x > 1)
    250 		{
    251 			int p = isP[x];
    252 			int cnt = 0;
    253 			while(x % p == 0)
    254 			{
    255 				cnt++;
    256 				x /= p;
    257 			}
    258 			cntP[p] = max(cntP[p], cnt);
    259 		}
    260 	}
    261 	bool ok = 1;
    262 	while(k > 1)
    263 	{
    264 		ok &= (cntP[isP[k]] > 0);
    265 		cntP[isP[k]]--;
    266 		k /= isP[k];
    267 	}
    268 	cout << (ok ? "Yes\n" : "No\n");
    269 }
    270 ```
    271 
    272 And a nice implementation by [Reyna](/profile/Reyna "International Grandmaster Reyna"): [18789803](/contest/687/submission/18789803 "Submission 18789803 by Reyna")
    273 
    274 ### [687C: The values you can make](//codeforces.com/contest/687/problem/C)
    275 
    276 #### Hint
    277 
    278 Use dynamic programming.
    279 
    280 #### Solution
    281 
    282 Let *dp**i*, *j*, *k* be true if and only if there exists a subset of the first *i* coins with sum *j*, that has a subset with sum *k*. There are 3 cases to handle:
    283 
    284 * The *i*-th coin is not used in the subsets.
    285 * The *i*-th coin is used in the subset to make *j*, but it's not used in the subset of this subset.
    286 * The *i*-th coin is used in both subsets.
    287 
    288 So *dp**i*, *j*, *k* is equal to *dp**i* - 1, *j*, *k* *OR* *dp**i* - 1, *j* - *c**i*, *k* *OR* *dp**i* - 1, *j* - *c**i*, *k* - *c**i*.
    289 
    290 The complexity is *O*(*nk*2).
    291 
    292 **C++ code**
    293 
    294 ```
    295 		//	   - -- --- ---- -----be name khoda----- ---- --- -- -		\\
    296 
    297 #include <bits/stdc++.h>
    298 using namespace std;
    299 
    300 inline int in() { int x; scanf("%d", &x); return x; }
    301 const int N = 505;
    302 
    303 bool dp[2][N][N];
    304 
    305 int main()
    306 {
    307 	int n, k;
    308 	cin >> n >> k;
    309 	dp[0][0][0] = 1;
    310 	for(int i = 1; i <= n; i++)
    311 	{
    312 		int now = i % 2;
    313 		int last = 1 - now;
    314 		int x = in();
    315 		for(int j = 0; j <= k; j++)
    316 			for(int y = 0; y <= j; y++)
    317 			{
    318 				dp[now][j][y] = dp[last][j][y];
    319 				if(j >= x)
    320 				{
    321 				    dp[now][j][y] |= dp[last][j - x][y];
    322 				    if(y >= x)
    323     					dp[now][j][y] |= dp[last][j - x][y - x];
    324 				}
    325 			}
    326 	}
    327 	vector <int> res;
    328 	for(int i = 0; i <= k; i++)
    329 		if(dp[n % 2][k][i])
    330 			res.push_back(i);
    331 	cout << res.size() << endl;
    332 	for(int x : res)
    333 		cout << x << " ";
    334 	cout << endl;
    335 }
    336 ```
    337 
    338 #### Challenge
    339 
    340 In the same constraints, output the numbers you can never not make! Formally, the values *x* such that for every subset of coins with the sum *k*, there exists a subset of this subset with the sum *x*.
    341 
    342 ### [687D: Dividing Kingdom II](//codeforces.com/contest/687/problem/D)
    343 
    344 Unfortunately, our mistake in setting the constrains for this problem made it possible to get Ac with *O*(*qm*) solution. We hope you accept our apology.
    345 
    346 #### Hint
    347 
    348 Consider the following algorithm to answer a single query: Sort the edges and add them one by one to the graph in decreasing order of their weights. The answer is weight of the first edge, which makes an odd cycle in the graph. Now show that there are only *O*(*n*) effective edges, which removing them may change the answer of the query. Use this idea to optimize your solution.
    349 
    350 #### Solution
    351 
    352 First, let’s solve a single query separately. Sort edges from interval [l, r] in decreasing order of weights. Using *dsu*, we can find longest prefix of these edges, which doesn’t contains odd cycle. (Graph will be bipartite after adding these edges.) The answer will be weight of the next edge. (We call this edge “bottleneck”).
    353 
    354 Why it's correct? Because if the answer is *w*, then the we can divide the graph in a way that none of the edges in the same part have value greater than *w*. So the graph induced by the edges with value greater than *w* must be bipartite. And if this graph is bipartite, then we can divide the graph into two parts as the bipartition, so no edge with value greater than *w* will be in the same part, and the answer is at most *w*.
    355 
    356 Let's have a look at this algorithm in more details. For each vertex, we keep two values in dsu: Its parent and if its part differs from its parent or not. We keep the second value equal to "parity of length of the path in original graph, between this node and its parent". We can divide the graph anytime into two parts, walking from one vertex to its parent and after reaching the root, see if the starting vertex must be in the same part as the root or not.
    357 
    358 In every connected component, there must not exist any edge with endpoints in the same part.
    359 
    360 After sorting the edges, there are 3 possible situations for an edge when we are adding it to the graph:
    361 
    362 1. The endpoints of this edge are between two different components of the current graph. Now we must merge these two components, and update the part of the root of one of the components.
    363 2. The endpoints of this edge are in the same component of the current graph, and they are in different parts of this component. There is nothing to do.
    364 3. The endpoints of this edge are in the same component of the current graph, and they are also in the same part of this component. This edge is the "bottleneck" and we can't keep our graph bipartite after adding it, so we terminate the algorithm.
    365 
    366 We call the edges of the first and the third type "valuable edges".
    367 
    368 The key observation is: If we run above algorithm on the valuable edges, the answer remains the same.
    369 
    370 Proof idea: The edges of the first type are spanning trees of connected components of the graph, and with a spanning tree of a bipartite graph, we can uniquely determine if two vertices are in the same part or not.
    371 
    372 So if we can ignore all other edges and run our algorithm on these valuable edges, we have *O*(*n*) edges instead of original *O*(*n*2) and the answer is the same.
    373 
    374 We answer the queries using a segment tree on the edges. In each node of this tree, we run the above algorithm and memorize the valuable edges. By implementing carefully (described [here](//codeforces.com/blog/entry/45770?#comment-303336)), making the segment tree could be done in ![](https://espresso.codeforces.com/322f39a0663aa20112104e53da25b5b437da1b80.png).
    375 
    376 Now for each query [*l*, *r*], you can decompose [*l*, *r*] into ![](https://espresso.codeforces.com/9040a33098f83986b0de64475c66584fbfdf0e22.png) segments in segment tree and each one has *O*(*n*) valuable edges. Running the naive algorithm on these edges lead to an ![](https://espresso.codeforces.com/5e7dae7c1838af7ba7570bdf02ff61029b043be6.png) solution for each query, which fits in time limit.
    377 
    378 **C++ code**
    379 
    380 ```
    381 	//     . .. ... .... ..... be name khoda ..... .... ... .. .     \\
    382 
    383 #include <bits/stdc++.h>
    384 using namespace std;
    385 
    386 inline int in() { int x; scanf("%d", &x); return x; }
    387 const int N = 2002, M = (1 << 20), Q = 1001, S = 2 * M;
    388 
    389 #define rank PAP
    390 
    391 struct Edge
    392 {
    393 	int u, v, w;
    394 	Edge(int u = 0, int v = 0, int w = 0):v(v), u(u), w(w) { }
    395 	bool operator <(const Edge &e) const { return w < e.w; }
    396 };
    397 
    398 struct Segment
    399 {
    400 	int l, r;
    401 	Segment(int l = 0, int r = 0): l(l), r(r) { }
    402 };
    403 
    404 typedef vector <Edge> Edges;
    405 
    406 int n, m, q;
    407 Edge es[M];
    408 Edges seg[S];
    409 Segment range[S];
    410 int par[N], cost[N], rank[N];
    411 
    412 Segment merge(Segment l, Segment r) { return Segment(l.l, r.r); }
    413 
    414 void clear(Edges &es)
    415 {
    416 	for(Edge e : es)
    417 	{
    418 		par[e.v] = par[e.u] = -1;
    419 		cost[e.v] = cost[e.u] = 0;
    420 		rank[e.v] = rank[e.u] = 1;
    421 	}
    422 }
    423 
    424 int root(int v) 
    425 { 
    426 	if(par[v] == -1)
    427 		return v;
    428 	int u = root(par[v]);
    429 	cost[v] ^= cost[par[v]];
    430 	return par[v] = u;
    431 }
    432 
    433 int parity(int v)
    434 {
    435 	root(v);
    436 	return cost[v];
    437 }
    438 
    439 int merge(Edge e)
    440 {
    441 	if(rank[root(e.u)] > rank[root(e.v)])
    442 		swap(e.u, e.v);
    443 	if(root(e.u) == root(e.v))
    444 	{
    445 		if(parity(e.u) == parity(e.v))
    446 			return 2;
    447 		return 0;
    448 	}
    449 	int u = root(e.u);
    450 	int v = root(e.v);
    451 	cost[u] ^= (parity(e.u) ^ 1 ^ parity(e.v));
    452 	par[u] = root(v);
    453 	rank[v] += rank[u];
    454 	return 1;
    455 }
    456 
    457 bool hasOddCycle;
    458 
    459 Edges merge(Edges &a, Edges &b)
    460 {
    461 	Edges c;
    462 	merge(a.begin(), a.end(), b.begin(), b.end(), back_inserter(c));
    463 	clear(c);
    464 	Edges res;
    465 	for(int i = c.size() - 1; i >= 0; i--)
    466 	{
    467 		int x = merge(c[i]);
    468 		if(x)
    469 			res.push_back(c[i]);
    470 		if(x == 2)
    471 		{
    472 			hasOddCycle = 1;
    473 			break;
    474 		}
    475 	}
    476 	reverse(res.begin(), res.end());
    477 	return res;
    478 }
    479 
    480 void make()
    481 {
    482 	for(int i = S - 1; i; i--)
    483 	{
    484 		if(i >= M)
    485 		{
    486 			range[i] = Segment(i - M, i - M + 1);
    487 			if(i - M < m)
    488 				seg[i].push_back(es[i - M]);
    489 		}
    490 		else
    491 		{
    492 			range[i] = merge(range[i * 2], range[i * 2 + 1]);
    493 			seg[i] = merge(seg[i * 2], seg[i * 2 + 1]);
    494 		}
    495 	}
    496 }
    497 
    498 int solve(Segment s)
    499 {
    500 	Edges es;
    501 	hasOddCycle = 0;
    502 	for(int l = s.l + M, r = s.r + M; l < r; l /= 2, r /= 2)
    503 	{
    504 		if(l % 2)
    505 			es = merge(es, seg[l++]);
    506 		if(r % 2)
    507 			es = merge(es, seg[--r]);
    508 	}
    509 	if(hasOddCycle)
    510 		return es[0].w;
    511 	return -1;
    512 }
    513 
    514 int main()
    515 {
    516 	cin >> n >> m >> q;
    517 	for(int i = 0; i < m; i++)
    518 	{
    519 		es[i].u = in() - 1;
    520 		es[i].v = in() - 1;
    521 		es[i].w = in();
    522 	}
    523 	make();
    524 	while(q--)
    525 	{
    526 		int l = in() - 1, r = in();
    527 		cout << solve(Segment(l, r)) << "\n";
    528 	}
    529 }
    530 ```
    531 
    532 ### [687E: TOF](//codeforces.com/contest/687/problem/E)
    533 
    534 #### Hint: What the actual problem is
    535 
    536 Looking at the code in the statement, you can see only the first edge in `neighbors` of each node is important. So for each vertex with at least one outgoing edge, you have to choose one edge and ignore the others. After this the graph becomes in the shape of some cycles with possible branches, and some paths. The number of `dfs` calls equals to 998 × ( sum of sizes of cycles ) + *n* +  number of cycles.
    537 
    538 #### Solution
    539 
    540 The goal is to minimize the sum of cycle sizes. Or, to maximize the number of vertices which are not in any cycle. Name them *good vertices*.
    541 
    542 * If there exists a vertex *v* without any outgoing edge, we can make all of the vertices that *v* is reachable from them good. Consider the dfs-tree from *v* in the reverse graph. You can choose the edge ![](https://espresso.codeforces.com/e19dbe2883bbff49400d4c262d7045cc75c6170f.png) from this tree as the first edge in `neighbors[u]`, in order to make all of these vertices good.
    543 * Vertices which are not in the sink strongly connected components could become good too, by choosing the edges from a path starting from them and ending in a sink strongly connected component.
    544 * In a sink strongly connected component, there exists a path from every vertex to others. So we can make every vertex good except a single cycle, by choosing the edges in the paths from other nodes to this cycle and the cycle edges.
    545 
    546 So, every vertices could become good except a single cycle in every sink strongly connected component. And the length of those cycles must be minimized, so we can choose the smallest cycle in every sink strongly connected component and make every other vertices good. Finding the smallest cycle in a graph with *n*-vertex and *m* edges could be done in *O*(*n*(*n* + *m*)) with running a *BFS* from every vertex, so finding the smallest cycle in every sink strongly connected component is *O*(*n*(*n* + *m*)) overall.
    547 
    548 **C++ code**
    549 
    550 ```
    551 	//     . .. ... .... ..... be name khoda ..... .... ... .. .     \\
    552 
    553 #include <bits/stdc++.h>
    554 using namespace std;
    555 
    556 inline int in() { int x; scanf("%d", &x); return x; }
    557 const int N = 5005;
    558 
    559 int comp[N], bfsDist[N], bfsPar[N];
    560 vector <int> g[N], gR[N];
    561 bool mark[N], inCycle[N];
    562 
    563 bool dfs(int v, vector <int> *g, vector <int> &nodes)
    564 {
    565 	mark[v] = 1;
    566 	for(int u : g[v])
    567 		if(!mark[u])
    568 			dfs(u, g, nodes);
    569 	nodes.push_back(v);
    570 }
    571 
    572 int findSmallestCycle(vector <int> vs)
    573 {
    574 	vector <int> cycle;
    575 	for(int root : vs)
    576 	{
    577 		for(int v : vs)
    578 		{
    579 			bfsDist[v] = 1e9;
    580 			bfsPar[v] = -1;
    581 		}
    582 		bfsDist[root] = 0;
    583 		queue <int> q;
    584 		q.push(root);
    585 		bool cycleFound = 0;
    586 		while(q.size() && !cycleFound)
    587 		{
    588 			int v = q.front();
    589 			q.pop();
    590 			for(int u : g[v])
    591 			{
    592 				if(u == root)
    593 				{
    594 					cycleFound = 1;
    595 					int curLen = bfsDist[v];
    596 					if(cycle.empty() || curLen < cycle.size())
    597 					{
    598 						cycle.clear();
    599 						for(; v != -1; v = bfsPar[v])
    600 							cycle.push_back(v);
    601 					}
    602 					break;
    603 				}
    604 				if(bfsDist[u] > bfsDist[v] + 1)
    605 				{
    606 					bfsDist[u] = bfsDist[v] + 1;
    607 					bfsPar[u] = v;
    608 					q.push(u);
    609 				}
    610 			}
    611 		}
    612 	}
    613 	return cycle.size();
    614 }
    615 
    616 int main()
    617 {
    618 	int n, m;
    619 	cin >> n >> m;
    620 	for(int i = 0; i < m; i++)
    621 	{
    622 		int u = in() - 1;
    623 		int v = in() - 1;
    624 		g[u].push_back(v);
    625 		gR[v].push_back(u);
    626 	}
    627 	vector <int> order;
    628 	for(int i = 0; i < n; i++)
    629 		if(!mark[i])
    630 			dfs(i, g, order);
    631 
    632 	fill(mark, mark + n, 0);
    633 	fill(comp, comp + n, -1);
    634 	int inCycle = 0, nCycle = 0;
    635 	for(; order.size(); order.pop_back())
    636 	{
    637 		int v = order.back();
    638 		if(mark[v])
    639 			continue;
    640 		vector <int> curComp;
    641 		dfs(v, gR, curComp);
    642 		bool isSink = true;
    643 		for(int u : curComp)
    644 			comp[u] = v;
    645 		for(int u : curComp)
    646 			for(int k = 0; k < g[u].size(); k++)
    647 				if(comp[g[u][k]] != v)
    648 					isSink = false;
    649 		if(isSink)
    650 		{
    651 			int x = findSmallestCycle(curComp);
    652 			if(x > 0)
    653 			{
    654 			    nCycle++;
    655 			    inCycle += x;
    656 			}
    657 		}
    658 	}
    659 	cout << 999 * inCycle + (n - inCycle) + nCycle << endl;
    660 
    661 }
    662 ```
    663 
    664 #### Challenge
    665 
    666 What if the target function is reversed? It means you have to choose a single outgoing edge from every node with at least one outgoing edge, and maximize the sum of cycle sizes in the chosen graph.
    667 
    668 I thought about this one a lot but can't find any solution. Do you have any idea?