codeforces-scrape

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

1770.md (39749B)


      1 Source: https://codeforces.com/blog/entry/110754
      2 
      3 ## [1770A - Koxia and Whiteboards](/contest/1770/problem/A "Good Bye 2022: 2023 is NEAR")
      4 
      5 Idea by [m_99](/profile/m_99 "International Grandmaster m_99")
      6 
      7 **Hint 1**
      8 
      9 Exactly $n$ items out of of $a_1,\ldots,a_n,b_1,\ldots,b_m$ will remain on the whiteboard at the end.
     10 
     11 **Hint 2**
     12 
     13 $b_m$ will always remain on the board at the end.
     14 
     15 **Hint 3**
     16 
     17 Consider the case where $n=2$ and $m=2$. As we mentioned in hint 2, $b_2$ will always be written, but what about $b_1$?
     18 
     19 **Solution**
     20 
     21 This problem can be solved naturally with a greedy algorithm — for $i = 1, 2, \dots, m$, we use $b_i$ to replace the minimal value among the current $a_1, a_2, \dots, a_n$. The time complexity is $O(nm)$ for each test case.
     22 
     23 Alternatively, we can first add $b_m$ to our final sum. For the remaining $(n+m-1)$ integers, we can freely pick $(n - 1)$ out of them and add it to our final sum. This is because if we want a certain $a_i$ to remain on the board at the end, we simply do not touch it in the process. If we want a certain $b_i$ to remain on the board at the end, then on the $i^{th}$ operation we replace some $a_j$ that we do not want at the end by $b_i$.
     24 
     25 Using an efficient sorting algorithm gives us a $O((n + m) \log (n + m))$ solution, which is our intended solution.
     26 
     27 **Code (m_99)**
     28 
     29 ```
     30 #include <stdio.h>
     31 #include <bits/stdc++.h>
     32 using namespace std;
     33 #define rep(i,n) for (int i = 0; i < (n); ++i)
     34 #define Inf32 1000000001
     35 #define Inf64 4000000000000000001
     36 
     37 int main(){
     38 	
     39 	int _t;
     40 	cin>>_t;
     41 	
     42 	rep(_,_t){
     43 		int n,m;
     44 		cin>>n>>m;
     45 		vector<long long> a(n+m);
     46 		rep(i,n+m)scanf("%lld",&a[i]);
     47 		
     48 		sort(a.begin(),a.end()-1);
     49 		reverse(a.begin(),a.end());
     50 		
     51 		long long ans = 0;
     52 		rep(i,n)ans += a[i];
     53 		
     54 		cout<<ans<<endl;
     55 	}
     56 	
     57 	
     58 	return 0;
     59 }
     60 ```
     61 
     62 ## [1770B - Koxia and Permutation](/contest/1770/problem/B "Good Bye 2022: 2023 is NEAR")
     63 
     64 Idea by [m_99](/profile/m_99 "International Grandmaster m_99")
     65 
     66 **Hint 1**
     67 
     68 For $k = 1$, the cost is always $2n$ for any permutation.
     69 
     70 **Hint 2**
     71 
     72 For $k \geq 2$, the minimal cost is always $n + 1$.
     73 
     74 **Solution**
     75 
     76 When $k = 1$ every permutation has the same cost.
     77 
     78 When $k \geq 2$, the minimal cost will be at least $n+1$. This is because there will always be at least one segment containing the element $n$ in the permutation, contributing $n$ to the "max" part of the sum, and the "min" part will add at least $1$ to the sum.
     79 
     80 In fact, the cost $n+1$ is optimal. It can be achieved by ordering the numbers in the pattern $[n, 1, n - 1, 2, n - 2, 3, n - 3, 4, \dots]$.
     81 
     82 The time complexity is $O(n)$ for each test case. Other careful constructions should also get Accepted.
     83 
     84 **Code (Nanako)**
     85 
     86 ```
     87 #include <iostream>
     88 #define MULTI int _T; cin >> _T; while(_T--)
     89 using namespace std;
     90 typedef long long ll;
     91  
     92 int n, k;
     93  
     94 int main () {
     95 	ios::sync_with_stdio(0);
     96 	cin.tie(0);
     97 	
     98 	MULTI {
     99 		cin >> n >> k;
    100 		int l = 1, r = n, _ = 1;
    101 		while (l <= r) cout << ((_ ^= 1) ? l++ : r--) << ' ';
    102 		cout << endl;
    103 	}
    104 }
    105 ```
    106 
    107 ## [1770C - Koxia and Number Theory](/contest/1770/problem/C "Good Bye 2022: 2023 is NEAR")
    108 
    109 Idea by [triple__a](/profile/triple__a "International Grandmaster triple__a")
    110 
    111 **Hint 1**
    112 
    113 If $a_i$ are not pairwise distinct we get a trivial NO.
    114 
    115 **Hint 2**
    116 
    117 If all $a_i$ are pairwise distinct, can you construct an example with $n = 4$ that gives an answer NO?
    118 
    119 **Hint 3**
    120 
    121 Perhaps you are thinking about properties such as parity? Try to generalize the idea.
    122 
    123 **Hint 3.5**
    124 
    125 Consider every prime. Consider Chinese Remainder Theorem.
    126 
    127 **Hint 4**
    128 
    129 How many primes should we check? Consider Pigeonhole Principle.
    130 
    131 **Solution**
    132 
    133 First, we should check whether the integers in $a$ are pairwise distinct, as $a_i + x \geq 2$ and $\gcd(t,t)=t$, which leads to a trivial NO.
    134 
    135 Given an integer $x$, let's define $b_i := a_i + x$. The condition "$\gcd(b_i,b_j)=1$ for $1\le i \lt j \le n$" is equivalent to "every prime $p$ should divides at most one $b_i$". Given a prime $p$, how should we verify whether for every $x \gt 0$, $p$ divides at least two elements in $b$?
    136 
    137 A small but guided sample is $a = [5, 6, 7, 8]$ with answer NO, because
    138 
    139 * $\gcd(6 + x, 8 + x) \neq 1$ if $x \equiv 0 \pmod 2$,
    140 * $\gcd(5 + x, 7 + x) \neq 1$ if $x \equiv 1 \pmod 2$.
    141 
    142 That is, if we consider $[5, 6, 7, 8]$ modulo $2$, we obtain the multiset ${1, 0, 1, 0}$. Both $0$ and $1$ appeared twice, so for any choice of $x$, exactly two integers in $b$ will be divided by $2$.
    143 
    144 This idea can be extended to larger primes. For a given prime $p$, let $cnt_j$ be the multiplicity of $j$ in the multiset $[ a_i \text{ mod } p, a_2 \text{ mod } p, \dots, a_n \text{ mod } p ]$. If $\min(\mathit{cnt}_0, \mathit{cnt}_1, \dots, \mathit{cnt}_{p-1}) \geq 2$, we output NO immediately.
    145 
    146 While there are many primes up to ${10}^{18}$, we only need to check for the primes up to $\lfloor \frac{n}{2} \rfloor$. This is because $\min(\mathit{cnt}_0, \mathit{cnt}_1, \dots, \mathit{cnt}_{p-1}) \geq 2$ is impossible for greater primes according to Pigeonhole Principle. Since the number of primes up to $\lfloor \frac{n}{2} \rfloor$ is at most $O\left(\frac{n}{\log n} \right)$, the problem can be solved in time $O\left(\frac{n^2}{\log n} \right)$.
    147 
    148 The reason that $\min(\mathit{cnt}) \geq 2$ is essential because for a prime $p$, if $a_u \equiv a_v \pmod p$, then it's necessary to have $(x + a_u) \not\equiv 0 \pmod p$, because $\gcd(x + a_u, x + a_v)$ will be divided by $p$ otherwise. So actually, $\mathit{cnt}_i \geq 2$ means $x \not\equiv (p-i) \pmod p$. If $\min(\mathit{cnt}) \lt 2$ holds for all primes, then we can list certain congruence equations and use [Chinese Reminder Theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem) to calculate a proper $x$; if there exists a prime that $\min(\mathit{cnt}) \geq 2$, then any choose of $x$ leads to the situation that $p$ appears twice.
    149 
    150 **Code (Nanako)**
    151 
    152 ```
    153 #include <iostream>
    154 #include <algorithm>
    155 #define MULTI int _T; cin >> _T; while(_T--)
    156 using namespace std;
    157 typedef long long ll;
    158  
    159 const int N = 105;
    160 const int INF = 0x3f3f3f3f;
    161 template <typename T> bool chkmin (T &x, T y) {return y < x ? x = y, 1 : 0;}
    162 template <typename T> bool chkmax (T &x, T y) {return y > x ? x = y, 1 : 0;}
    163  
    164 int n;
    165 ll a[N];
    166  
    167 int cnt[N];
    168  
    169 int main () {
    170 	ios::sync_with_stdio(0);
    171 	cin.tie(0);
    172 	
    173 	MULTI {
    174 		cin >> n;
    175 		for (int i = 1;i <= n;++i) {
    176 			cin >> a[i];
    177 		}
    178 		
    179 		int isDistinct = 1;
    180 		sort(a + 1, a + n + 1);
    181 		for (int i = 1;i <= n - 1;++i) {
    182 			if (a[i] == a[i + 1]) isDistinct = 0;
    183 		}
    184 		if (isDistinct == 0) {
    185 			cout << "NO" << endl;
    186 			continue;
    187 		}
    188 		
    189 		int CRT_able = 1;
    190 		for (int mod = 2;mod <= n / 2;++mod) {
    191 			fill(cnt, cnt + mod, 0);
    192 			for (int i = 1;i <= n;++i) {
    193 				cnt[a[i] % mod]++;
    194 			}
    195 			if (*min_element(cnt, cnt + mod) >= 2) CRT_able = 0;
    196 		}
    197 		cout << (CRT_able ? "YES" : "NO") << endl;
    198 	}
    199 }
    200 ```
    201 
    202 ## [1770D - Koxia and Game](/contest/1770/problem/D "Good Bye 2022: 2023 is NEAR")
    203 
    204 Idea by [m_99](/profile/m_99 "International Grandmaster m_99")
    205 
    206 **Hint 1**
    207 
    208 If all of $a$, $b$ and $c$ are fixed, how to determine who will win?
    209 
    210 **Hint 2**
    211 
    212 If $a$ and $b$ are fixed, design an algorithm to check if there is an array $c$ that makes Koxia wins.
    213 
    214 **Hint 2.5**
    215 
    216 If you can't solve the problem in Hint 2, try to think about how it's related to graph theory.
    217 
    218 **Hint 3**
    219 
    220 Try to discuss the structure of components in the graph to count up the number of $c$.
    221 
    222 **Solution**
    223 
    224 Firstly, let's consider how an array $c$ could make Koxia wins.
    225 
    226 **Lemma 1.** In each round, Koxia should remove an element in $S$ to make the remaining $2$ elements in $S$ the same (i.e. Mahiru's choice determined nothing actually).
    227 
    228 * In round $n$, if Koxia leaves two choices for Mahiru then Mahiru will be able to prevent $d$ from being a permutation.
    229 * This means if Koxia wins, there is only one choice for $d_n$.
    230 * Now $(d_1, d_2, \dots, d_{n-1})$ have to be a permutation of a specific $n-1$ numbers. Apply the same argument on $d_{n-1}$ and so on, we can conclude that every $d_i$ only has one choice if Koxia wins.
    231 
    232 **Lemma 2.** Let $p$ be array of length $n$ where we can set $p_i$ to either $a_i$ or $b_i$. Koxia wins iff there exists a way to make $p$ a permutation.
    233 
    234 * According to Lemma 1, if there is a way to make $p$ a permutation, we can just set $c_i = p_i$. Koxia can then force Mahiru to set $d_i = p_i$ every round and Koxia will win.
    235 * If it is impossible to make $p$ a permutation, Mahiru can pick either $a_i$ or $b_i$ (at least one of them is available) every round. The resulting array $d$ is guaranteed to not be a permutation.
    236 
    237 First, we need an algorithm to determine if there is a way to make $p$ a permutation.
    238 
    239 We can transform this into a graph problem where $(a_i, b_i)$ are edges in a graph with $n$ vertices. Then there is a way to make $p$ a permutation iff there is a way to assign a direction for every edge such that every vertex has one edge leading into it. It is not hard to see that this is equivalent to the condition that for every connected component, the number of edges equals the number of vertices. We can verify this by a Disjoint-Set Union or a graph traversal in $O(n \alpha(n))$ or $O(n)$ time complexity.
    240 
    241 To solve the counting problem, we consider the structure of the connected components one by one. A component with $|V| = |E|$ can be viewed as a tree with an additional edge. This additional edge can be categorized into two cases:
    242 
    243 * The additional edge forms a cycle together with some of the other edges. There are $2$ choices for the cycle (clockwise and counterclockwise), and the choices of other edges are fixed then (point away from the cycle).
    244 * The additional edge forms a self-loop. Then the value of $c_i$ determines nothing in this situation so it can be any integers in $[1, n]$, and the choices of all other edges are fixed.
    245 
    246 Therefore, if exists at least one $c$ to make Koxia wins, then the answer is $2^{\textrm{cycle component cnt}} \cdot n^{\textrm{self-loop component cnt}}$. The time complexity is $O(n \alpha(n))$ or $O(n)$.
    247 
    248 **Code (Nanako, DSU)**
    249 
    250 ```
    251 #include <iostream>
    252 #include <numeric>
    253 #define MULTI int _T; cin >> _T; while(_T--)
    254 using namespace std;
    255 typedef long long ll;
    256  
    257 const int N = 1e5 + 5;
    258 const int mod = 998244353;
    259  
    260 int n;
    261 int a[N], b[N];
    262  
    263 int fa[N], cnt_v[N], cnt_e[N], selfloop[N];
    264 int vis[N];
    265 void init () {
    266 	iota(fa + 1, fa + n + 1, 1);
    267 	fill(cnt_v + 1, cnt_v + n + 1, 1);
    268 	fill(cnt_e + 1, cnt_e + n + 1, 0);
    269 	fill(selfloop + 1, selfloop + n + 1, 0);
    270 	fill(vis + 1, vis + n + 1, 0);
    271 }
    272 int getfa (int x) {
    273 	return fa[x] == x ? x : fa[x] = getfa(fa[x]);
    274 }
    275 void merge (int u, int v) {
    276 	u = getfa(u);
    277 	v = getfa(v);
    278 	cnt_v[u] += cnt_v[v];
    279 	cnt_e[u] += cnt_e[v];
    280 	selfloop[u] |= selfloop[v];
    281 	fa[v] = u;
    282 }
    283  
    284 int main () {
    285 	ios::sync_with_stdio(0);
    286 	cin.tie(0);
    287 	
    288 	MULTI {
    289 		cin >> n;
    290 		for (int i = 1;i <= n;++i) {
    291 			cin >> a[i];
    292 		}
    293 		for (int i = 1;i <= n;++i) {
    294 			cin >> b[i];
    295 		}
    296 		
    297 		init();
    298 		for (int i = 1;i <= n;++i) {
    299 			if (getfa(a[i]) != getfa(b[i])) merge(a[i], b[i]);
    300 			cnt_e[getfa(a[i])]++;
    301 			if (a[i] == b[i]) selfloop[getfa(a[i])] = 1;
    302 		}
    303 		
    304 		ll ans = 1;
    305 		for (int i = 1;i <= n;++i) if (vis[getfa(i)] == 0) {
    306 			if (cnt_v[getfa(i)] != cnt_e[getfa(i)]) ans = 0;
    307 			else ans = ans * (selfloop[getfa(i)] ? n : 2) % mod;
    308 			vis[getfa(i)] = 1;
    309 		}
    310 		cout << ans << endl;
    311 	}
    312 }
    313 ```
    314 
    315 **Code (zengminghao, DFS)**
    316 
    317 ```
    318 #include <bits/stdc++.h>
    319 using namespace std;
    320 const int N = 1e5 + 5;
    321 const int P = 998244353;
    322  
    323 int n, a[N], b[N];
    324 vector <int> G[N];
    325 bool vis[N];
    326  
    327 int vertex, edge, self_loop;
    328 void dfs(int x) {
    329 	if (vis[x]) return ;
    330 	vis[x] = true;
    331 	vertex++;
    332 	for (auto y : G[x]) {
    333 		edge++;
    334 		dfs(y);
    335 		if (y == x) {
    336 			self_loop++;
    337 		}
    338 	}
    339 }
    340  
    341 void solve() {
    342 	scanf("%d", &n);
    343 	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    344 	for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
    345 	
    346 	for (int i = 1; i <= n; i++) G[i].clear();
    347 	
    348 	for (int i = 1; i <= n; i++) {
    349 		G[a[i]].push_back(b[i]);
    350 		G[b[i]].push_back(a[i]);
    351 	}
    352 	
    353 	int ans = 1;
    354 	
    355 	for (int i = 1; i <= n; i++) vis[i] = false;
    356 	for (int i = 1; i <= n; i++) {
    357 		if (vis[i]) continue ;
    358 		vertex = 0;
    359 		edge = 0;
    360 		self_loop = 0;
    361 		dfs(i);
    362 		if (edge != 2 * vertex) {
    363 			ans = 0;
    364 		} else if (self_loop) {
    365 			ans = 1ll * ans * n % P;
    366 		} else {
    367 			ans = ans * 2 % P;
    368 		}
    369 	}
    370 	
    371 	printf("%d\n", ans);
    372 }
    373  
    374 int main() {
    375 	int t;
    376 	scanf("%d", &t);
    377 	while (t--) {
    378 		solve();
    379 	}
    380 	return 0;
    381 }
    382 ```
    383 
    384 ## [1770E - Koxia and Tree](/contest/1770/problem/E "Good Bye 2022: 2023 is NEAR")
    385 
    386 Idea by [m_99](/profile/m_99 "International Grandmaster m_99")
    387 
    388 **Hint 1**
    389 
    390 Solve a classic problem — find the sum of pairwise distances of $k$ chosen nodes in a tree.
    391 
    392 **Hint 2**
    393 
    394 If we add the move operations while the direction of edges are fixed, find the sum of pairwise distances of $k$ chosen nodes.
    395 
    396 **Hint 2.5**
    397 
    398 If you can't solve the problem in Hint 2, consider why writers make each edge passed by butterflies for at most once.
    399 
    400 **Hint 3**
    401 
    402 When the direction of edges become random, how maintaining $p_i$ as the possibility of "node $i$ contains a butterfly" help you to get the answer?
    403 
    404 **Solution**
    405 
    406 At first sight, we usually think of a classic problem — find the sum of pairwise distances of $k$ chosen nodes in a tree. For any edge, if there are $x$ chosen nodes and $n - x$ chosen nodes respectively on each side of it, then there will be $x (n - x)$ pairs of nodes passing this edge. Without loss of generality, let's assign node $1$ as root, and define both $\mathit{siz}_i$ as the number of chosen nodes in subtree $i$. By summing up $\mathit{siz}_{\mathit{son}} (n - \mathit{siz}_{\mathit{son}})$ for each edge $(\mathit{fa}, \mathit{son})$, we derive the answer, which equals to the expected value of the distance of two nodes (Uniformly randomly chosen from $k$ nodes) after dividing by $\binom{k}{2}$.
    407 
    408 Let's turn to Hint 2 then — add the move operations while the direction of edges are fixed. Let's define $\mathit{siz}^0_i$ and $\mathit{siz}_i$ as the number of butterflies in subtree $i$, but before any move operation / in real time respectively. A very important observation is, although butterflies are moving, we can always claim $|\mathit{siz}_{\mathit{son}} - \mathit{siz}^0_{\mathit{son}}| \leq 1$ because each edge is passed by butterflies for at most once. This property allows us to discuss different values of $\mathit{siz}_{\mathit{son}}$ to sum up the answer in constant time complexity, if you maintain butterflies' positions correctly.
    409 
    410 When we introduce random directions additionally, if we define $p_i$ as the possibility of "node $i$ contains a butterfly", then an equivalent statement of move operation from node $u$ to node $v$ will be, actually, set $p_u = p_v = \frac{p_u+p_v}{2}$, which allows us to maintain $p$ in real time easily. Similarly, by discussing values of $\mathit{siz}_{\mathit{son}}$ (but with possibilities of each case instead of specified moves), we get the final answer. The total time complexity is $O(n)$.
    411 
    412 **Code (Nanako)**
    413 
    414 ```
    415 #include <iostream>
    416 #include <vector>
    417 using namespace std;
    418 typedef long long ll;
    419  
    420 const int N = 3e5 + 5;
    421 const int mod = 998244353;
    422 const int inv2 = 499122177;
    423  
    424 ll qpow (ll n, ll m) {
    425 	ll ret = 1;
    426 	while (m) {
    427 		if (m & 1) ret = ret * n % mod;
    428 		n = n * n % mod;
    429 		m >>= 1;
    430 	}
    431 	return ret;
    432 }
    433 ll getinv (ll a) {
    434 	return qpow(a, mod - 2);
    435 }
    436  
    437 int n, k;
    438 int a[N];
    439 int u[N], v[N];
    440  
    441 vector <int> e[N];
    442 int fa[N];
    443 ll p[N], sum[N];
    444 void dfs (int u, int f) {
    445 	sum[u] = p[u];
    446 	for (int v : e[u]) if (v != f) {
    447 		dfs(v, u);
    448 		fa[v] = u;
    449 		sum[u] += sum[v];
    450 	}
    451 }
    452  
    453 int main () {
    454 	ios::sync_with_stdio(0);
    455 	cin.tie(0);
    456 	
    457 	cin >> n >> k;
    458 	for (int i = 1;i <= k;++i) {
    459 		cin >> a[i];
    460 		p[a[i]] = 1;
    461 	}
    462 	for (int i = 1;i <= n - 1;++i) {
    463 		cin >> u[i] >> v[i];
    464 		e[u[i]].push_back(v[i]);
    465 		e[v[i]].push_back(u[i]);
    466 	}
    467 	dfs(1, -1);
    468 	
    469 	ll ans = 0;
    470 	for (int i = 1;i <= n - 1;++i) {
    471 		if (fa[u[i]] == v[i]) swap(u[i], v[i]);
    472 		ll puv = p[u[i]] * (1 - p[v[i]] + mod) % mod;
    473 		ll pvu = p[v[i]] * (1 - p[u[i]] + mod) % mod;
    474 		ll delta = 0;
    475 		delta -= puv * sum[v[i]] % mod * (k - sum[v[i]]) % mod;
    476 		delta -= pvu * sum[v[i]] % mod * (k - sum[v[i]]) % mod;
    477 		delta += puv * (sum[v[i]] + 1) % mod * (k - sum[v[i]] - 1) % mod;
    478 		delta += pvu * (sum[v[i]] - 1) % mod * (k - sum[v[i]] + 1) % mod;
    479 		ans = (ans + sum[v[i]] * (k - sum[v[i]]) + delta * inv2) % mod;
    480 		ans = (ans % mod + mod) % mod;
    481 		p[u[i]] = p[v[i]] = 1ll * (p[u[i]] + p[v[i]]) * inv2 % mod;
    482 	}
    483 	cout << ans * getinv(1ll * k * (k - 1) / 2 % mod) % mod << endl;
    484 }
    485 ```
    486 
    487 ## [1770F - Koxia and Sequence](/contest/1770/problem/F "Good Bye 2022: 2023 is NEAR")
    488 
    489 Idea by [m_99](/profile/m_99 "International Grandmaster m_99")
    490 
    491 **Hint 1**
    492 
    493 From symmetry, for any non-negative integer $t$, the number of good sequences with $a_1=t$, the number of good sequences with $a_2=t$, ... are equal.
    494 
    495 **Hint 2**
    496 
    497 It is useful to consider the contribution of each bit to the answer independently.
    498 
    499 **Hint 3**
    500 
    501 Since XOR is undone twice, considering the contribution to the answer can be regarded as counting up over mod $2$.
    502 
    503 **Hint 4**
    504 
    505 It is difficult to count those for which total or is $y$, but it is relatively easy to count those for which total or is a subset of $y$. Then, we can consider a way using the inclusion-exclusion principle.
    506 
    507 **Hint 5**
    508 
    509 Lucas's theorem and Kummer's theorem are useful. In particular, you can derive equivalence conditions on or.
    510 
    511 **Hint 6**
    512 
    513 "There are $a+b$ white balls. For every pair $(c,d)$ of nonnegative integers satisfying $c+d=n$, find the sum of the ways to choose $c$ balls from the first $a$ balls and $d$ balls from the remaining $b$ balls." The answer to this problem is $_{a+b} C_{n}$. This is because considering how to choose for every pair $(c,d)$ of non-negative integers satisfying $c+d=n$ merely consider the case of choosing $n$ balls as how many balls to choose from $a$ balls and $b$ balls. This result is called Vandermonde's identity.
    514 
    515 **Solution**
    516 
    517 Let $f(i,t)$ is the number of good sequence such that $a_i=t$. $f(1,t)=f(2,t)=...=f(n,t)$, so if $n$ is even, the answer is $0$. Otherwise, the answer is total xor of $t$ such that number of good sequences such that $a_1=t$ is odd. We can consider each bit independently, so we can rewrite the problem "for each $i$, find the number of good sequences such that $a_1$'s $i$-th bit is $1$, modulo $2$".
    518 
    519 Let $g(y')$ is the answer if $y$ is a subset of $y'$(means $y \mid y'=y'$). We can prove with induction the answer of the original problem is total xor of $g(y')$ such that $y'$ is a subset of given $y$. So, the goal is for each $i$, find the number of $y'$ such that $y'$ is a subset of $y$ and $g(y')$'s $i$-th bit is $1$, modulo $2$.
    520 
    521 We can prove with Lucas's theorem or Kummer's theorem ($p=2$), "$\binom{a}{b} \bmod 2$ is $1$" is equivalent to "$b$ is a subset of $a$". The number of sequences such that the length is $n$ and total sum is $x$ and total or is a subset of $y$, modulo $2$ is equal to $\sum_{t_1+\ldots+t_n=x} \prod{} \binom{y}{t_i}$, because if there is $t_i$ which is not a subset of $y$, $\binom{y}{t_i}$ is $0$ and the product is also $0$, modulo $2$. Consider Vandermonde's identity, the value is equal to $\binom{ny}{x}$. In a similar way, we can rewrite the problem to "for each $i$, find the number of $y'$ such that $y'$ is a subset of $y$ and $y'$'s $i$-th bit is $1$ and $x-2^i$ is a subset of $ny'-2^i$($\binom{ny'-2^i}{x-2^i} \bmod 2 = 1$), modulo $2$".
    522 
    523 From the above, we can solve this problem in $O(y \log y)$ by performing the calculation in $O(1)$ for all $i$ and all $y'$.
    524 
    525 **Code (errorgorn)**
    526 
    527 ```
    528 #include <bits/stdc++.h>
    529 using namespace std;
    530  
    531 #define int long long
    532 #define ll long long
    533 #define ii pair<ll,ll>
    534 #define iii pair<ii,ll>
    535 #define fi first
    536 #define se second
    537 #define endl '\n'
    538 #define debug(x) cout << #x << ": " << x << endl
    539  
    540 #define pub push_back
    541 #define pob pop_back
    542 #define puf push_front
    543 #define pof pop_front
    544 #define lb lower_bound
    545 #define ub upper_bound
    546  
    547 #define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
    548 #define all(x) (x).begin(),(x).end()
    549 #define sz(x) (int)(x).size()
    550  
    551 mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
    552  
    553 int n,a,b;
    554  
    555 bool isSub(int i,int j){
    556 	if (i<0 || j<0) return false;
    557 	return (j&i)==i;
    558 }
    559  
    560 signed main(){
    561 	ios::sync_with_stdio(0);
    562 	cin.tie(0);
    563 	cout.tie(0);
    564 	cin.exceptions(ios::badbit | ios::failbit);
    565 	
    566 	cin>>n>>a>>b;
    567 	
    568 	int ans=0;
    569 	for (int sub=b;sub;sub=(sub-1)&b) rep(bit,0,20) if (sub&(1<<bit)){
    570 		if (isSub(a-(1<<bit),n*sub-(1<<bit))){
    571 			ans^=(1<<bit);
    572 		}
    573 	}
    574 	
    575 	cout<<ans*(n%2)<<endl;
    576 }
    577 ```
    578 
    579 ## [1770G - Koxia and Bracket](/contest/1770/problem/G "Good Bye 2022: 2023 is NEAR")
    580 
    581 Idea by [huangxiaohua](/profile/huangxiaohua "Grandmaster huangxiaohua") and [errorgorn](/profile/errorgorn "International Grandmaster errorgorn")
    582 
    583 **Hint 1**
    584 
    585 What special properties does the deleted bracket sequence have?
    586 
    587 **Hint 2**
    588 
    589 Try to solve this with $O(n^2)$ DP.
    590 
    591 **Hint 3**
    592 
    593 If there is no balance requirement, can multiple brackets be processed quickly with one operation?
    594 
    595 **Hint 4**
    596 
    597 Can you combine the last idea with divide-and-conquer or something?
    598 
    599 **Solution**
    600 
    601 #### $O(n^2)$ Solution
    602 
    603 Let us consider what properties the removed bracket subsequence has.
    604 
    605 First, it must be a bracket subsequence in the form `))...)((....(`. The proof is simple: if there is a deleted `)` on the right-hand side of a `(`, then we can keep them in $s$ without breaking the balancing property of the remaining sequence.
    606 
    607 This property means that we can divide the string into $2$ parts. We only delete `)` from the first part and only delete `(` from the second part. Now let us try to find the dividing point between the two parts: Consider a prefix sum based on a sequence of brackets in which each `(` is replaced by 1 and each `)` is replaced by -1.
    608 
    609 We define a position as a *special position* if and only if the number corresponding to this position is less than the previously occurring minimum value. It is easy to see that whenever a special position occurs, we must remove an additional `)` before this position to make the bracket sequence satisfy the condition again.
    610 
    611 Considering the above idea, we can find that only the `)` before the farthest special position may be deleted, so we can use this position as the dividing point.
    612 
    613 We now solve two separate problems. However, we can turn the problem on deleting only '(' into the one on deleting only `)`. For example, if we are only allowed to delete `(` from `(()((()())`, it is equivalent to the number of ways to delete only `)` from `(()()))())`.
    614 
    615 For the part where only `)` is deleted, the sufficient condition for it to be a balanced bracket sequence is that each number in the prefix sum must be greater than 0 after the operation.
    616 
    617 Also considering the above ideas, let us define the state $dp_{i,j}$, which represents after removing the breakets required by special position, the number of ways to delete additional $j$ $(j \geq 0)$ occurrence of `)` from the string up the $i$-th occurrence of `)` in the string.
    618 
    619 $ \begin{equation} dp_{i,j} = \begin{cases} dp_{i-1,j}+dp_{i-1,j-1}, & \text{if } i \text{ is not special}; \\ dp_{i-1,j}+dp_{i-1,j+1}, & \text{if } i \text{ is special}. \end{cases} \end{equation} $
    620 
    621 Multiply the $dp_{end,0}$ obtained from both parts of the string to obtain the answer. The time complexity is $O(n^2)$ and optimized implementations can run in about 9 seconds, but it is not enough to pass.
    622 
    623 #### $O(n\sqrt{n \log n})$ Solution
    624 
    625 Let's try to optimize the transitions when there are no special positions. For state $dp_{i,j}$, after processing $k$ individual `)`, the transitions are as follows:
    626 
    627 $dp_{i+k,j}=\sum_{l=0}^k \binom{k}{l} \times dp_{i,j-l}$
    628 
    629 We find that this transfer equation behaves as a polynomial convolution. Thus we can optimize this convolution by NTT with a time complexity of $O(n \log n)$ for a single operation, while the worst global complexity of this Solution is $O(n^2 \log n)$ due to the presence of the special position.
    630 
    631 Consider how this Solution can be combined with the $O(n^2)$ Solution. For states $dp_{i,j}$ where we want to consider its contribution to $dp_{i+k}$, if $j \geq k$ is satisfied, then the transitions are not affected by the special position anyway.
    632 
    633 Based on the above idea, we can adopt a mixed Solution based on periodic reconstruction: set the reconstruction period $B$, and within one round of the period, we use the $O(n^2)$ DP Solution to handle the part of $j \le B$, while for the part of $j \gt B$, we compute the answer by NTT after one round of the period.
    634 
    635 The time complexity $O(\frac{n^2}{B}+B\cdot n \log n)$ can be optimized to $O(n\sqrt{n \log n})$ by setting the appropriate $B$. Although the time complexity is still high, given the low constant factor of the $O(n^2)$ solution, a decently-optimized implementation is able to get AC.
    636 
    637 #### $O(n\log^2 n)$ Solution
    638 
    639 Consider combining the idea of extracting $j \geq k$ parts for NTT with divide-and-conquer. Suppose now that the interval to be processed is $(l,r)$, where the DP polynomial passed is $s$. We proceed as follows:
    640 
    641 * Count the number of special positions $num$ in the interval $(l,r)$, extract the part of the polynomial $s$ corresponding to the state $j \geq num$, and convolute it with the current interval alone.
    642 * Pass the part of the polynomial $s$ corresponding to the state $j \lt num$ into the interval $(l,mid)$, and then pass the result into the interval $(mid+1,r)$ to continue the operation.
    643 * Add the polynomials obtained by the above two steps directly, and return the obtained polynomial.
    644 
    645 How to calculate the time complexity of performing the above operations? Let's analyze the operations passed into the left interval and the right interval separately.
    646 
    647 * When passing in the left interval $(l,mid)$, the size of the polynomial for the NTT operation is the number of special positions in the interval $(l,r)$ minus the number of special positions in the left interval $(l,mid)$, i.e., the number of special positions in the right interval $(mid+1,r)$, which does not exceed the length of the right interval $(mid+1,r)$.
    648 * When passed into the right interval $(mid+1,r)$, the size of the polynomial does not exceed the length of the left interval $(l,mid)$.
    649 * Also, the length of the combinatorial polynomial multiplied with $s$ is the interval length + 1.
    650 
    651 In summary, the size of the two polynomials for the NTT operation in the interval $(l,r)$ does not exceed the interval length + 1. Thus the time complexity of this solution is divide-and-conquer combined with the time complexity of NTT, i.e. $O(n \log^2 n)$.
    652 
    653 **Code (errorgorn)**
    654 
    655 ```
    656 #include <bits/stdc++.h>
    657 #include <ext/pb_ds/assoc_container.hpp>
    658 #include <ext/pb_ds/tree_policy.hpp>
    659 #include <ext/rope>
    660 using namespace std;
    661 using namespace __gnu_pbds;
    662 using namespace __gnu_cxx;
    663  
    664 #define int long long
    665 #define ll long long
    666 #define ii pair<ll,ll>
    667 #define iii pair<ii,ll>
    668 #define fi first
    669 #define se second
    670 #define endl '\n'
    671 #define debug(x) cout << #x << ": " << x << endl
    672  
    673 #define pub push_back
    674 #define pob pop_back
    675 #define puf push_front
    676 #define pof pop_front
    677 #define lb lower_bound
    678 #define ub upper_bound
    679  
    680 #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
    681 #define all(x) (x).begin(),(x).end()
    682 #define sz(x) (int)(x).size()
    683  
    684 #define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
    685 //change less to less_equal for non distinct pbds, but erase will bug
    686  
    687 mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
    688  
    689 const int MOD=998244353;
    690  
    691 ll qexp(ll b,ll p,int m){
    692     ll res=1;
    693     while (p){
    694         if (p&1) res=(res*b)%m;
    695         b=(b*b)%m;
    696         p>>=1;
    697     }
    698     return res;
    699 }
    700  
    701 ll inv(ll i){
    702 	return qexp(i,MOD-2,MOD);
    703 }
    704  
    705 ll fix(ll i){
    706 	i%=MOD;
    707 	if (i<0) i+=MOD;
    708 	return i;
    709 }
    710  
    711 ll fac[1000005];
    712 ll ifac[1000005];
    713  
    714 ll nCk(int i,int j){
    715 	if (i<j) return 0;
    716 	return fac[i]*ifac[j]%MOD*ifac[i-j]%MOD;
    717 }
    718  
    719 //https://github.com/kth-competitive-programming/kactl/blob/main/content/numerical/NumberTheoreticTransform.h
    720 const ll mod = (119 << 23) + 1, root = 62; // = 998244353
    721 // For p < 2^30 there is also e.g. 5 << 25, 7 << 26, 479 << 21
    722 // and 483 << 21 (same root). The last two are > 10^9.
    723 typedef vector<int> vi;
    724 typedef vector<ll> vl;
    725 void ntt(vl &a) {
    726 	int n = sz(a), L = 31 - __builtin_clz(n);
    727 	static vl rt(2, 1);
    728 	for (static int k = 2, s = 2; k < n; k *= 2, s++) {
    729 		rt.resize(n);
    730 		ll z[] = {1, qexp(root, mod >> s, mod)};
    731 		rep(i,k,2*k) rt[i] = rt[i / 2] * z[i & 1] % mod;
    732 	}
    733 	vi rev(n);
    734 	rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
    735 	rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);
    736 	for (int k = 1; k < n; k *= 2)
    737 		for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {
    738 			ll z = rt[j + k] * a[i + j + k] % mod, &ai = a[i + j];
    739 			a[i + j + k] = ai - z + (z > ai ? mod : 0);
    740 			ai += (ai + z >= mod ? z - mod : z);
    741 		}
    742 }
    743 vl conv(const vl &a, const vl &b) {
    744 	if (a.empty() || b.empty()) return {};
    745 	int s = sz(a) + sz(b) - 1, B = 32 - __builtin_clz(s), n = 1 << B;
    746 	int inv = qexp(n, mod - 2, mod);
    747 	vl L(a), R(b), out(n);
    748 	L.resize(n), R.resize(n);
    749 	ntt(L), ntt(R);
    750 	rep(i,0,n) out[-i & (n - 1)] = (ll)L[i] * R[i] % mod * inv % mod;
    751 	ntt(out);
    752 	return {out.begin(), out.begin() + s};
    753 }
    754  
    755 vector<int> v;
    756  
    757 vector<int> solve(int l,int r,vector<int> poly){
    758 	if (poly.empty()) return poly;
    759 	
    760 	if (l==r){
    761 		poly=conv(poly,{1,1});
    762 		poly.erase(poly.begin(),poly.begin()+v[l]);
    763 		return poly;
    764 	}
    765 	
    766 	int m=l+r>>1;
    767 	int num=0;
    768 	rep(x,l,r+1) num+=v[x];
    769 	num=min(num,sz(poly));
    770 	
    771 	vector<int> small(poly.begin(),poly.begin()+num);
    772 	poly.erase(poly.begin(),poly.begin()+num);
    773 	
    774 	vector<int> mul;
    775 	rep(x,0,r-l+2) mul.pub(nCk(r-l+1,x));
    776 	poly=conv(poly,mul);
    777 	
    778 	small=solve(m+1,r,solve(l,m,small));
    779 	poly.resize(max(sz(poly),sz(small)));
    780 	rep(x,0,sz(small)) poly[x]=(poly[x]+small[x])%MOD;
    781 	
    782 	return poly;
    783 }
    784  
    785 int solve(string s){
    786 	if (s=="") return 1;
    787 	v.clear();
    788 	
    789 	int mn=0,curr=0;
    790 	for (auto it:s){
    791 		if (it=='(') curr++;
    792 		else{
    793 			curr--;
    794 			if (curr<mn){
    795 				mn=curr;
    796 				v.pub(1);
    797 			}
    798 			else{
    799 				v.pub(0);
    800 			}
    801 		}
    802 	}
    803 	
    804 	return solve(0,sz(v)-1,{1})[0];
    805 }
    806  
    807 int n;
    808 string s;
    809 int pref[500005];
    810  
    811 signed main(){
    812 	ios::sync_with_stdio(0);
    813 	cin.tie(0);
    814 	cout.tie(0);
    815 	cin.exceptions(ios::badbit | ios::failbit);
    816 	
    817 	fac[0]=1;
    818 	rep(x,1,1000005) fac[x]=fac[x-1]*x%MOD;
    819 	ifac[1000004]=inv(fac[1000004]);
    820 	rep(x,1000005,1) ifac[x-1]=ifac[x]*x%MOD;
    821 	
    822 	cin>>s;
    823 	n=sz(s);
    824 	pref[0]=0;
    825 	rep(x,0,n) pref[x+1]=pref[x]+(s[x]=='('?1:-1);
    826 	
    827 	int pos=min_element(pref,pref+n+1)-pref;
    828 	string a=s.substr(0,pos),b=s.substr(pos,n-pos);
    829 	reverse(all(b)); for (auto &it:b) it^=1;
    830 	cout<<solve(a)*solve(b)%MOD<<endl;
    831 }
    832 ```
    833 
    834 ## [1770H - Koxia, Mahiru and Winter Festival](/contest/1770/problem/H "Good Bye 2022: 2023 is NEAR")
    835 
    836 Idea by [SteamTurbine](/profile/SteamTurbine "International Master SteamTurbine")
    837 
    838 **Hint 1**
    839 
    840 In what scenario the maximum congestion is $1$?
    841 
    842 **Hint 2**
    843 
    844 Assume you have a blackbox that can solve any problem instance of size $n-2$, use it to solve a problem instance of size $n$.
    845 
    846 **Preface**
    847 
    848 This is a special case for a problem called *congestion minimization*. While in general this problem is NP-hard, for this special structure it can be solved efficiently.
    849 
    850 The only case where the maximum congestion is $1$, is when $p = q = [1,2,\dots,n]$. This can be proved by a pigeonhole argument — if there exists some $p_i \neq i$ or $q_i \neq i$, the total length of the $2n$ paths will be strictly greater than the number of edges which means at least one edge has to be used more than once.
    851 
    852 Our goal now is to try constructing a routing scheme with maximum congestion $2$. We will show that this is always doable for any input. We will first show a pictorial sketch that presents the idea, and fill in the details later.
    853 
    854 We also provide you a python script that visualize the output to help you debug, you can find it at the end of this section.
    855 
    856 **Solution (sketch)**
    857 
    858 ![ ](/predownloaded/8c/35/8c35980cc2ee8bf561e40ffe9177a698a7d93e4f.jpg) ![ ](/predownloaded/02/2f/022f7c2105614ddc96176cef011fe977028f943a.jpg) ![ ](/predownloaded/11/54/1154c085ae11c0e67958e85a0551804a414bd56b.jpg) ![ ](/predownloaded/65/d7/65d7f01a57fdd7dbf97ca38fa44362b454cd9961.jpg)
    859 
    860 **Solution (details)**
    861 
    862 The solution is based on induction. The base cases $n=0$ and $n=1$ are trivial. Now assume we can solve any problem instance for size up to $k-2$. We will treat it as a blackbox to solve a problem instance of size $k$.
    863 
    864 Given any problem instance of size $k$, first we route the following $4$ demand pairs using only the outer edges:
    865 
    866 * the top-bottom pair that starts at $(1, 1)$, using the left and bottom edges;
    867 * the top-bottom pair that starts at $(1, k)$, using the right and bottom edges;
    868 * the left-right pair that starts at $(1, 1)$, using the top and right edges;
    869 * the left-right pair that ends at $(1,k)$, using the left and top edges. However, if this is the same pair as above, then we route another arbitrary left-right pair using the left, top and right edges.
    870 
    871 As of now, there are $k-2$ top-bottom demands and $k-2$ left-right demands remain to be routed. We simply connect their starting and ending points one step closer to the center, retaining their relative order. In such way, we reduced the problem to a problem instance of size $k-2$ which we already knew how to solve.
    872 
    873 **Code (SteamTurbine)**
    874 
    875 ```
    876 #include <bits/stdc++.h>
    877 #define FOR(i,s,e) for (int i=(s); i<(e); i++)
    878 #define FOE(i,s,e) for (int i=(s); i<=(e); i++)
    879 #define FOD(i,s,e) for (int i=(s)-1; i>=(e); i--)
    880 #define PB push_back
    881 using namespace std;
    882 
    883 struct Paths{
    884 	/* store paths in order */
    885 	vector<vector<pair<int, int>>> NS, EW;
    886 	
    887 	Paths(){
    888 		NS.clear();
    889 		EW.clear();
    890 	}
    891 };
    892 
    893 Paths solve(vector<int> p, vector<int> q){
    894 	int n = p.size();
    895 	Paths Ret;
    896 	Ret.NS.resize(n);
    897 	Ret.EW.resize(n);
    898 	
    899 	// Base case
    900 	if (n == 0) return Ret;
    901 	if (n == 1){
    902 		Ret.NS[0].PB({1, 1});
    903 		Ret.EW[0].PB({1, 1});
    904 		return Ret;
    905 	}
    906 
    907 	// Route NS flow originating from (1, 1) and (1, n) using leftmost and rightmost edges
    908 	FOE(i,1,n){
    909 		Ret.NS[0].PB({i, 1});
    910 		Ret.NS[n-1].PB({i, n});
    911 	}
    912 	// Routing to final destination using bottom edges
    913 	FOE(i,2,p[0]) Ret.NS[0].PB({n, i});
    914 	FOD(i,n,p[n-1]) Ret.NS[n-1].PB({n, i});
    915 
    916 	// Create p'[] for n-2 instance
    917 	vector<int> p_new(0);
    918 	FOE(i,1,n-2) p_new.PB(p[i] - (p[i]>p[0]) - (p[i]>p[n-1]));
    919 
    920 	// Route EW flow originating from (1, 1) using topmost and rightmost edges
    921 	FOE(i,1,n) Ret.EW[0].PB({1, i});
    922 	FOE(i,2,q[0]) Ret.EW[0].PB({i, n});
    923 
    924 	// Route EW flow originating in (m, 1) with q[m] as small as possible
    925 	int m = 1;
    926 	// special handle so congestion is 1 if possible
    927 	if (p[0] == 1 && p[n-1] == n && q[0] == 1 && q[n-1] == n){
    928 		m = n - 1;
    929 		FOE(i,1,n) Ret.EW[n-1].PB({n, i});
    930 	}
    931 	else{
    932 		FOR(i,1,n) if (q[i] < q[m]) m = i;
    933 		// Route(m+1, 1) --> (1, 1) --> (1, n) --> (q[m], n)
    934 		
    935 		FOD(i,m+2,2) Ret.EW[m].PB({i, 1});
    936 		FOR(i,1,n) Ret.EW[m].PB({1, i});
    937 		FOE(i,1,q[m]) Ret.EW[m].PB({i, n});
    938 	}
    939 	
    940 	// Create q'[] for n-2 instance
    941 	vector<int> q_new(0);
    942 	FOR(i,1,n) if (i != m) q_new.PB(q[i] - (q[i]>q[0]) - (q[i]>q[m]));
    943 
    944 	if (n > 1){
    945 		Paths S = solve(p_new, q_new);
    946 		int t;
    947 		
    948 		// connect NS paths
    949 		FOR(i,1,n-1){
    950 			Ret.NS[i].PB({1, i+1});
    951 			for (auto [x, y]: S.NS[i-1]){
    952 				Ret.NS[i].PB({x+1, y+1});
    953 				t = y + 1;
    954 			}
    955 			Ret.NS[i].PB({n, t});
    956 			if (p[i] != t) Ret.NS[i].PB({n, p[i]});
    957 		}
    958 
    959 		// connect EW paths
    960 		int l = 0;
    961 		FOR(i,1,n) if (i != m){
    962 			Ret.EW[i].PB({i+1, 1});
    963 			if (i > m) Ret.EW[i].PB({i, 1});
    964 			
    965 			for (auto [x, y]: S.EW[l]){
    966 				Ret.EW[i].PB({x+1, y+1});
    967 				t = x + 1;
    968 			}
    969 			
    970 			Ret.EW[i].PB({t, n});
    971 			if (q[i] != t) Ret.EW[i].PB({q[i], n});
    972 			++l;
    973 		}
    974 	}
    975 
    976 	return Ret;
    977 }
    978 
    979 int main(){
    980 	int n;
    981 	vector<int> p, q;
    982 	
    983 	scanf("%d", &n);
    984 	p.resize(n), q.resize(n);
    985 	FOR(i,0,n) scanf("%d", &p[i]);
    986 	FOR(i,0,n) scanf("%d", &q[i]);
    987 
    988 	Paths Solution = solve(p, q);
    989 	
    990 	for (auto path: Solution.NS){
    991 		printf("%d", path.size());
    992 		for (auto [x, y]: path) printf(" %d %d", x, y);
    993 		puts("");
    994 	}
    995 	
    996 	for (auto path: Solution.EW){
    997 		printf("%d", path.size());
    998 		for (auto [x, y]: path) printf(" %d %d", x, y);
    999 		puts("");
   1000 	}
   1001 	return 0;
   1002 }
   1003 ```
   1004 
   1005 **Visualizer (Python script)**
   1006 
   1007 ```
   1008 # ---------------------------------------------------  
   1009 # Visualize the ouput
   1010 # Pass the output as stdin to the script
   1011 # Only works for output with congestion at most 2
   1012 # Code by SteamTurbine Dec 2022
   1013 # ---------------------------------------------------
   1014 
   1015 from PIL import Image, ImageDraw, ImageColor
   1016 from sys import stdin
   1017 import random
   1018 
   1019 # Visual the ouput
   1020 # Pass the output as stdin to the script
   1021 
   1022 Lines = [line for line in stdin if len(line.strip()) > 0]       
   1023 n = int(len(Lines)/2)
   1024 
   1025 im = Image.new('RGB', (n*150+200, n*150+200), (255, 255, 255))
   1026 draw = ImageDraw.Draw(im)
   1027 
   1028 S = {(0,0,0,0)}
   1029 Dict = {}
   1030 Colors = ['orange', 'blue', 'green', 'red', 'skyblue', 'olive', 'brown', 'yellow', 'gray', 'tomato', 'tan' , 'purple', 'cyan', 'skyblue']
   1031 
   1032 # use color map if n is large
   1033 if (n+n > len(Colors)):
   1034     Colors = []
   1035     for name, code in ImageColor.colormap.items():
   1036         if (name != "black" and name != "white"): Colors.append(name)
   1037     random.shuffle(Colors)
   1038 
   1039 # draw blank lines
   1040 # lines to down
   1041 for i in range(1, n+1, 1):
   1042     for j in range(1, n, 1):
   1043         draw.line((i*150+20, j*150+20, i*150+20, j*150+170), fill = 'black', width = 5)
   1044 
   1045 # lines to right
   1046 for i in range(1, n, 1):
   1047     for j in range(1, n+1, 1):
   1048         draw.line((i*150+20, j*150+20, i*150+170, j*150+20), fill = 'black', width = 5)
   1049 
   1050 for i in range(len(Lines)):
   1051     line = Lines[i]
   1052     arr = [int(x) for x in line.split()] 
   1053     pathlen = arr[0]            
   1054     color = Colors[i % len(Colors)]
   1055     
   1056     # draw source and sink
   1057     if (i >= n):
   1058         # x from 0 to n
   1059         y = arr[1]
   1060         x = arr[2]
   1061         draw.line((x*150-40, y*150+20, x*150+20, y*150+20), fill=color, width=12)
   1062         y = arr[len(arr)-2]
   1063         x = arr[len(arr)-1]
   1064         draw.line((x*150+20, y*150+20, x*150+80, y*150+20), fill=color, width=12)
   1065     else:
   1066         # y from 0 to n
   1067         y = arr[1]
   1068         x = arr[2]
   1069         draw.line((x*150+20, y*150-40, x*150+20, y*150+20), fill=color, width=12)
   1070         y = arr[len(arr)-2]
   1071         x = arr[len(arr)-1]
   1072         draw.line((x*150+20, y*150+20, x*150+20, y*150+80), fill=color, width=12)         
   1073     
   1074     for k in range(3, len(arr), 2):        
   1075         (y1, x1, y2, x2) = arr[k-2:k+2]
   1076         
   1077         if (x1 > x2): (x1, y1, x2, y2) = (x2, y2, x1, y1)
   1078         elif (x1 == x2) and (y1 > y2): (x1, y1, x2, y2) = (x2, y2, x1, y1)
   1079         
   1080         # check if set used
   1081         if ((x1, y1, x2, y2) in S):
   1082             old_color = Dict[(x1, y1, x2, y2)]
   1083             used = 1
   1084         else:
   1085             used = 0
   1086             S.add((x1, y1, x2, y2))
   1087             Dict[(x1, y1, x2, y2)] = color
   1088                
   1089         # drawline
   1090         if (x1 == x2):
   1091             if (used):
   1092                 draw.line((x1*150+26, y1*150+20, x2*150+26, y2*150+20), fill=old_color, width=12)            
   1093                 draw.line((x1*150+14, y1*150+20, x2*150+14, y2*150+20), fill=color, width=12)
   1094             else: draw.line((x1*150+20, y1*150+20, x2*150+20, y2*150+20), fill=color, width=12)            
   1095         else:
   1096             if (used):
   1097                 draw.line((x1*150+20, y1*150+26, x2*150+20, y2*150+26), fill=old_color, width=12)
   1098                 draw.line((x1*150+20, y1*150+14, x2*150+20, y2*150+14), fill=color, width=12)
   1099             else: draw.line((x1*150+20, y1*150+20, x2*150+20, y2*150+20), fill=color, width=12)
   1100             
   1101 # draw nodes
   1102 for i in range(1, n+1, 1):
   1103     for j in range(1, n+1, 1):
   1104         draw.ellipse((i*150, j*150, i*150+40, j*150+40), fill = 'white', outline = 'black', width = 5)
   1105 
   1106 im.show()
   1107 im.save("problemF.png")
   1108 ```