codeforces-scrape

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

2249.md (51640B)


      1 Source: https://codeforces.com/blog/entry/155516
      2 
      3 ## [2250A - Threshold Movement](/contest/2250/problem/A "Codeforces Round 1112 (Div. 2)")
      4 
      5 * Idea:[aaa_Pigeon2](/profile/aaa_Pigeon2 "International Grandmaster aaa_Pigeon2")
      6 * Solution:[aaa_Pigeon2](/profile/aaa_Pigeon2 "International Grandmaster aaa_Pigeon2")
      7 
      8 **Solution**
      9 
     10 Let us determine what is required for every position to contain exactly one element after the simultaneous move.
     11 
     12 The element initially at position $1$ cannot move to the left, so it must move to the right. Therefore, $w_1 \gt k$. Once it leaves, only the element initially at position $2$ can fill position $1$, so $w_2 \lt k$.
     13 
     14 Thus, the elements at positions $1$ and $2$ must swap. Repeating the same argument for the remaining positions, the only possible movement pattern is
     15 
     16 $ 1\leftrightarrow 2,\quad 3\leftrightarrow 4,\quad 5\leftrightarrow 6,\ldots $
     17 
     18 Consequently, $n$ must be even, every element at an odd position must move to the right, and every element at an even position must move to the left.
     19 
     20 Let
     21 
     22 $ L=\max_{i\bmod 2=0}w_i,\qquad R=\min_{i\bmod 2=1}w_i. $
     23 
     24 We need an integer $k$ such that $L \lt k \lt R$. Such an integer exists if and only if $L+2\le R$.
     25 
     26 The time complexity is $O(n)$ per test case, and the extra space complexity is $O(1)$.
     27 
     28 **Code**
     29 
     30 ```
     31 #include <bits/stdc++.h>
     32 using namespace std;
     33 
     34 void work() {
     35 	int n; cin >> n;
     36 	long long L = 0, R = 1000000001LL;
     37 
     38 	for (int i = 1; i <= n; ++i) {
     39 		long long w; cin >> w;
     40 		if (i & 1) R = min(R, w);
     41 		else L = max(L, w);
     42 	}
     43 
     44 	cout << (n % 2 == 0 && L + 2 <= R ? "YES" : "NO") << '\n';
     45 }
     46 
     47 int main() {
     48 	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
     49 
     50 	int T; cin >> T;
     51 	while (T--) work();
     52 
     53 	return 0;
     54 }
     55 ```
     56 
     57 ## [2250B - String Construction](/contest/2250/problem/B "Codeforces Round 1112 (Div. 2)")
     58 
     59 * Idea:[_MCYYDS_](/profile/_MCYYDS_ "Grandmaster _MCYYDS_")
     60 * Solution:[_MCYYDS_](/profile/_MCYYDS_ "Grandmaster _MCYYDS_")
     61 
     62 **Hint 1**
     63 
     64 Partition the string into maximal blocks of equal characters. How does the number of blocks determine the number of adjacent equal pairs?
     65 
     66 **Solution**
     67 
     68 Define a block as a maximal consecutive segment of equal characters. Suppose the string has $r$ blocks with lengths $l_1,l_2,\ldots,l_r$. A block of length $l_i$ contributes exactly $l_i-1$ adjacent equal pairs, so the total number is
     69 
     70 $ \sum_{i=1}^{r}(l_i-1)=n-r. $
     71 
     72 Therefore, we need to construct a string with exactly $r=n-k$ blocks.
     73 
     74 Because $k \lt n$, we have $r\ge1$. Since $n\ge2$ and the counts of $\mathtt{0}$ and $\mathtt{1}$ may differ by at most $1$, both characters must appear, so the string must contain at least two blocks. Hence, when $r=1$, or equivalently $k=n-1$, no solution exists.
     75 
     76 Now assume $r\ge2$. Let the block characters alternate, starting with $\mathtt{0}$. The numbers of $\mathtt{0}$-blocks and $\mathtt{1}$-blocks are
     77 
     78 $ r_0=\left\lceil\frac r2\right\rceil,\qquad r_1=\left\lfloor\frac r2\right\rfloor. $
     79 
     80 We want the total numbers of the two characters to be
     81 
     82 $ c_0=\left\lceil\frac n2\right\rceil,\qquad c_1=\left\lfloor\frac n2\right\rfloor. $
     83 
     84 First assign one character to each block. This uses $r_0$ zeros and $r_1$ ones. Since $r\le n$, we have $r_0\le c_0$ and $r_1\le c_1$.
     85 
     86 Append all remaining zeros to any $\mathtt{0}$-block and all remaining ones to any $\mathtt{1}$-block, then concatenate the blocks in order. The two character counts differ by at most $1$, and the string has exactly $r$ blocks, so it contains exactly $n-r=k$ adjacent equal pairs.
     87 
     88 The time complexity is $O(n)$ per test case and $O(\sum n)$ in total. The space complexity is $O(n)$.
     89 
     90 **Code**
     91 
     92 ```
     93 #include <bits/stdc++.h>
     94 using namespace std;
     95 
     96 void work() {
     97 	int n, k; cin >> n >> k;
     98 
     99 	if (n > 1 && k == n - 1) {
    100 		cout << -1 << '\n';
    101 		return;
    102 	}
    103 
    104 	k = n - k;
    105 	int c0 = (n + 1) / 2, c1 = n / 2;
    106 
    107 	for (int i = 1; i <= k; ++i) {
    108 		if (i & 1) {
    109 			if (i + 2 > k) {
    110 				while (c0--) cout << 0;
    111 			}
    112 			else {
    113 				--c0;
    114 				cout << 0;
    115 			}
    116 		}
    117 		else {
    118 			if (i + 2 > k) {
    119 				while (c1--) cout << 1;
    120 			}
    121 			else {
    122 				--c1;
    123 				cout << 1;
    124 			}
    125 		}
    126 	}
    127 	cout << '\n';
    128 }
    129 
    130 int main() {
    131 	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    132 
    133 	int T; cin >> T;
    134 	while (T--) work();
    135 
    136 	return 0;
    137 }
    138 ```
    139 
    140 ## [2249A - Rank Subsequence](/contest/2249/problem/A "Codeforces Round 1112 (Div. 1)")
    141 
    142 * Idea:[aaa_Pigeon2](/profile/aaa_Pigeon2 "International Grandmaster aaa_Pigeon2")
    143 * Solution:[aaa_Pigeon2](/profile/aaa_Pigeon2 "International Grandmaster aaa_Pigeon2")
    144 
    145 **Hint 1**
    146 
    147 An element's rank from the right depends on both its position in the retained subsequence and the subsequence's final length.
    148 
    149 **Hint 2**
    150 
    151 Enumerate the final retained length $m$. Once $m$ is fixed, the condition for every position in the subsequence is fixed.
    152 
    153 **Solution**
    154 
    155 Whether an element can occupy the $j$-th position of the retained subsequence depends on the final length $m$, because its rank from the right is $m-j+1$.
    156 
    157 Therefore, we enumerate the final length $m$.
    158 
    159 For a fixed $m$, scan the original sequence from left to right and fill positions $1,2,\ldots,m$ of the subsequence in order. When filling position $j$, element $i$ can be chosen if and only if
    160 
    161 $ j\notin[l_i,r_i] $
    162 
    163 and
    164 
    165 $ m-j+1\notin[u_i,v_i]. $
    166 
    167 Whenever the current element satisfies both conditions, choose it immediately.
    168 
    169 To prove this greedy choice, suppose a feasible solution chooses an element $x$ for position $j$, while the greedy algorithm chooses an earlier valid element $y$. Replacing $x$ with $y$ leaves every later element of the original solution available and does not reduce the remaining suffix in which subsequent choices must be made. Thus, whenever a feasible solution exists, the greedy algorithm also succeeds.
    170 
    171 Enumerate $m$ from $n$ down to $1$. The first feasible value is the maximum possible answer. If no positive value is feasible, the answer is $0$.
    172 
    173 The time complexity is $O(n^2)$ per test case, and the space complexity is $O(n)$.
    174 
    175 **Code**
    176 
    177 ```
    178 #include <bits/stdc++.h>
    179 using namespace std;
    180 
    181 const int N = 5000;
    182 
    183 int n;
    184 int l[N + 10], r[N + 10], u[N + 10], v[N + 10];
    185 
    186 bool check(int m) {
    187 	int j = 1;
    188 
    189 	for (int i = 1; i <= n && j <= m; ++i) {
    190 		int x = m - j + 1;
    191 		if ((j < l[i] || j > r[i]) && (x < u[i] || x > v[i])) ++j;
    192 	}
    193 
    194 	return j == m + 1;
    195 }
    196 
    197 void work() {
    198 	cin >> n;
    199 	for (int i = 1; i <= n; ++i) cin >> l[i] >> r[i] >> u[i] >> v[i];
    200 
    201 	for (int m = n; m >= 1; --m) {
    202 		if (!check(m)) continue;
    203 		cout << m << '\n';
    204 		return;
    205 	}
    206 
    207 	cout << 0 << '\n';
    208 }
    209 
    210 int main() {
    211 	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    212 
    213 	int T; cin >> T;
    214 	while (T--) work();
    215 
    216 	return 0;
    217 }
    218 ```
    219 
    220 ## [2249B - Permutation Cuts](/contest/2249/problem/B "Codeforces Round 1112 (Div. 1)")
    221 
    222 * Idea:[aaa_Pigeon2](/profile/aaa_Pigeon2 "International Grandmaster aaa_Pigeon2")
    223 * Solution:[aaa_Pigeon2](/profile/aaa_Pigeon2 "International Grandmaster aaa_Pigeon2")
    224 
    225 **Hint 1**
    226 
    227 The value $n$ lies on exactly one side of every cut. Therefore, the value of the cut must be the maximum on the opposite side.
    228 
    229 **Hint 2**
    230 
    231 Enumerate the dividing point determined by the position of $n$. The cut values to its left must be non-decreasing, while those to its right must be non-increasing.
    232 
    233 **Hint 3**
    234 
    235 Merge the left sequence with the reversed right sequence. The first occurrence of a value forces its position, while every later occurrence contributes a number of choices.
    236 
    237 **Solution**
    238 
    239 First observe that no cut value can equal $n$. The value $n$ lies on exactly one side of a cut, while the maximum on the opposite side is at most $n-1$. Therefore, if some $a_i=n$, the answer is $0$.
    240 
    241 Now consider the position of $n$. For cut $i$:
    242 
    243 * If $n$ lies on the right, then $a_i$ is the maximum of the prefix on the left.
    244 * If $n$ lies on the left, then $a_i$ is the maximum of the suffix on the right.
    245 
    246 Hence, there must be a dividing point $c$ such that $a_1,\ldots,a_c$ is non-decreasing and $a_{c+1},\ldots,a_{n-1}$ is non-increasing. If both parts are non-empty, we must also have $a_c\ne a_{c+1}$. These two maxima are attained at positions on opposite sides of the dividing point, and a permutation cannot contain the same value at both positions.
    247 
    248 We enumerate all values of $c$ satisfying these conditions. There may seem to be many candidates, but the indices belonging to both the non-decreasing prefix and the non-increasing suffix can only form a segment of equal values. Two adjacent equal values cannot form an internal boundary, so only a constant number of candidates need to be considered.
    249 
    250 After fixing $c$, merge
    251 
    252 $ a_1,a_2,\ldots,a_c $
    253 
    254 with the reversed right part
    255 
    256 $ a_{n-1},a_{n-2},\ldots,a_{c+1} $
    257 
    258 to obtain one non-decreasing sequence. Process its $i$-th value $x$:
    259 
    260 * If this is the first occurrence of $x$, then the maximum on that side must become $x$ at this position, so the assigned permutation value is forced to be $x$.
    261 * Otherwise, we may assign any unused value smaller than $x$. Since $i-1$ values have already been used, there are $x-i+1$ choices.
    262 
    263 For each repeated occurrence, multiply the answer by $x-i+1$. This gives the number of permutations corresponding to the fixed dividing point. Finally, sum these values over all valid dividing points.
    264 
    265 Each merge takes $O(n)$ time. Since only a constant number of dividing points are valid, the time complexity is $O(n)$ per test case, and the space complexity is $O(n)$.
    266 
    267 **Code**
    268 
    269 ```
    270 #include <bits/stdc++.h>
    271 using namespace std;
    272 
    273 const int N = 1000000;
    274 const int mod = 998244353;
    275 
    276 int n;
    277 int a[N + 10], vis[N + 10];
    278 bool pre[N + 10], suf[N + 10];
    279 
    280 void work() {
    281 	cin >> n;
    282 	for (int i = 1; i < n; ++i) cin >> a[i];
    283 	a[n] = 0;
    284 
    285 	for (int i = 1; i < n; ++i) {
    286 		if (a[i] != n) continue;
    287 		cout << 0 << '\n';
    288 		return;
    289 	}
    290 
    291 	pre[0] = 1;
    292 	for (int i = 1; i < n; ++i) pre[i] = pre[i - 1] && a[i] >= a[i - 1];
    293 	suf[n] = 1;
    294 	for (int i = n - 1; i >= 1; --i) suf[i] = suf[i + 1] && a[i] >= a[i + 1];
    295 
    296 	long long ans = 0;
    297 	for (int cut = 0; cut < n; ++cut) {
    298 		if (!pre || !suf[cut + 1]) continue;
    299                 if (cut > 0 && cut < n - 1 && a[cut] == a[cut + 1]) continue;
    300 
    301 	        vector<int> l, r;
    302 	        for (int i = 1; i <= cut; ++i) l.push_back(a[i]);
    303 	        for (int i = cut + 1; i < n; ++i) r.push_back(a[i]);
    304 	        reverse(r.begin(), r.end());
    305 
    306 		memset(vis, 0, sizeof(int) * (n + 1));
    307 		int x = 0, y = 0, used = 0;
    308 		long long ways = 1;
    309 
    310 		while (x < (int)l.size() || y < (int)r.size()) {
    311 			int w;
    312 			if (x == (int)l.size()) w = r[y++];
    313 			else if (y == (int)r.size()) w = l[x++];
    314 			else if (l[x] < r[y]) w = l[x++];
    315 			else if (l[x] > r[y]) w = r[y++];
    316 			else {
    317 				cout << 0 << '\n';
    318 				return;
    319 			}
    320 
    321 			if (!vis[w]) vis[w] = 1;
    322 			else if (w < used) ways = 0;
    323 			else ways = ways * (w - used) % mod;
    324 			++used;
    325 		}
    326 
    327 		ans += ways;
    328 	}
    329 
    330 	cout << ans % mod << '\n';
    331 }
    332 
    333 int main() {
    334 	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    335 
    336 	int T; cin >> T;
    337 	while (T--) work();
    338 
    339 	return 0;
    340 }
    341 ```
    342 
    343 ## [2249C - Double-Rift Dial](/contest/2249/problem/C "Codeforces Round 1112 (Div. 1)")
    344 
    345 * Idea:[aaa_Pigeon2](/profile/aaa_Pigeon2 "International Grandmaster aaa_Pigeon2")
    346 * Solution:[aaa_Pigeon2](/profile/aaa_Pigeon2 "International Grandmaster aaa_Pigeon2")
    347 
    348 **Hint 1**
    349 
    350 Duplicate the permutation so that the cyclic sequence starting at any position becomes an ordinary contiguous segment of the duplicated array.
    351 
    352 **Hint 2**
    353 
    354 After inserting a new value $x$, the change in the number of consecutive-value blocks depends only on whether $x-1$ and $x+1$ have already appeared.
    355 
    356 **Hint 3**
    357 
    358 Maintain the number of blocks for all starting positions simultaneously. Once a starting position has produced more than two blocks, it can be discarded permanently.
    359 
    360 **Solution**
    361 
    362 Checking every prefix separately for every starting position would introduce an additional factor of $n$. Instead, duplicate the permutation and define
    363 
    364 $ q_i=p_{((i-1)\bmod n)+1}. $
    365 
    366 For a starting position $l$, the successive cyclic prefixes become the ordinary segments $[l,l],[l,l+1],\ldots,[l,l+n-1]$.
    367 
    368 Enumerate the right endpoint $r$ from left to right. When $q_r$ is inserted, the starting positions whose current segment ends at $r$ form the interval
    369 
    370 $ L=\max(1,r-n+1),\qquad R=\min(r,n). $
    371 
    372 Let the new value be $x$. Because the current segment has length at most $n$, no permutation value appears twice. The change in the number of consecutive-value blocks is
    373 
    374 $ \Delta=1-[x-1\text{ has already appeared}]-[x+1\text{ has already appeared}]. $
    375 
    376 We first regard $x$ as a new block, then merge it with the block on either side whenever the corresponding neighboring value has already appeared.
    377 
    378 To update all starting positions simultaneously, let $\operatorname{last}_v$ be the latest position before $r$ at which value $v$ appeared. For a starting position $l$, value $v$ appears in $[l,r-1]$ if and only if $\operatorname{last}_v\ge l$.
    379 
    380 Therefore, inserting $x$ requires only three range additions:
    381 
    382 1. Add $1$ to $[L,R]$.
    383 2. If $x-1$ exists, subtract $1$ from $[L,\min(R,\operatorname{last}_{x-1})]$.
    384 3. If $x+1$ exists, subtract $1$ from $[L,\min(R,\operatorname{last}_{x+1})]$.
    385 
    386 Use a lazy segment tree to maintain the current number of blocks for every starting position, with range addition and a global maximum query. Once a starting position has more than two blocks, it has already produced an invalid prefix. A later decrease cannot erase that earlier invalid prefix, so the starting position can be removed permanently.
    387 
    388 Each starting position is removed at most once. We process $2n-1$ right endpoints, performing only a constant number of range operations for each one. Thus, the time complexity is $O(n\log n)$, and the space complexity is $O(n)$.
    389 
    390 **Code**
    391 
    392 ```
    393 #include <bits/stdc++.h>
    394 using namespace std;
    395 
    396 const int N = 200000;
    397 const int inf = 1000000000;
    398 
    399 int n;
    400 int p[N + 10], last[N + 10];
    401 int mx[4 * N + 10], lazy[4 * N + 10];
    402 
    403 void apply(int u, int v) {
    404 	mx[u] += v;
    405 	lazy[u] += v;
    406 }
    407 
    408 void push(int u) {
    409 	if (!lazy[u]) return;
    410 	apply(u << 1, lazy[u]);
    411 	apply(u << 1 | 1, lazy[u]);
    412 	lazy[u] = 0;
    413 }
    414 
    415 void add(int u, int l, int r, int ql, int qr, int v) {
    416 	if (ql <= l && r <= qr) {
    417 		apply(u, v);
    418 		return;
    419 	}
    420 
    421 	push(u);
    422 	int mid = (l + r) >> 1;
    423 	if (ql <= mid) add(u << 1, l, mid, ql, qr, v);
    424 	if (qr > mid) add(u << 1 | 1, mid + 1, r, ql, qr, v);
    425 	mx[u] = max(mx[u << 1], mx[u << 1 | 1]);
    426 }
    427 
    428 void add(int l, int r, int v) {
    429 	if (l <= r) add(1, 1, n, l, r, v);
    430 }
    431 
    432 int find_bad(int u, int l, int r) {
    433 	if (l == r) return l;
    434 
    435 	push(u);
    436 	int mid = (l + r) >> 1;
    437 	if (mx[u << 1] > 2) return find_bad(u << 1, l, mid);
    438 	return find_bad(u << 1 | 1, mid + 1, r);
    439 }
    440 
    441 void del(int u, int l, int r, int x) {
    442 	if (l == r) {
    443 		mx[u] = -inf;
    444 		lazy[u] = 0;
    445 		return;
    446 	}
    447 
    448 	push(u);
    449 	int mid = (l + r) >> 1;
    450 	if (x <= mid) del(u << 1, l, mid, x);
    451 	else del(u << 1 | 1, mid + 1, r, x);
    452 	mx[u] = max(mx[u << 1], mx[u << 1 | 1]);
    453 }
    454 
    455 void work() {
    456 	cin >> n;
    457 	for (int i = 1; i <= n; ++i) cin >> p[i];
    458 
    459 	memset(last, 0, sizeof(int) * (n + 2));
    460 	memset(mx, 0, sizeof(int) * (4 * n + 5));
    461 	memset(lazy, 0, sizeof(int) * (4 * n + 5));
    462 
    463 	int ans = n;
    464 	for (int r = 1; r < 2 * n; ++r) {
    465 		int L = max(1, r - n + 1), R = min(r, n);
    466 		int x = p[(r - 1) % n + 1];
    467 
    468 		add(L, R, 1);
    469 		if (x > 1 && last[x - 1] >= L) add(L, min(R, last[x - 1]), -1);
    470 		if (x < n && last[x + 1] >= L) add(L, min(R, last[x + 1]), -1);
    471 		last[x] = r;
    472 
    473 		while (mx[1] > 2) {
    474 			int x = find_bad(1, 1, n);
    475 			del(1, 1, n, x);
    476 			--ans;
    477 		}
    478 	}
    479 
    480 	cout << ans << '\n';
    481 }
    482 
    483 int main() {
    484 	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    485 
    486 	int T; cin >> T;
    487 	while (T--) work();
    488 
    489 	return 0;
    490 }
    491 ```
    492 
    493 ## [2249D - Xor Permutation Matrix](/contest/2249/problem/D "Codeforces Round 1112 (Div. 1)")
    494 
    495 * Idea:[aaa_Pigeon2](/profile/aaa_Pigeon2 "International Grandmaster aaa_Pigeon2")
    496 * Solution:[aaa_Pigeon2](/profile/aaa_Pigeon2 "International Grandmaster aaa_Pigeon2")
    497 
    498 **Hint 1**
    499 
    500 Compare two adjacent rows. For a fixed pair of rows, the $2\times2$ condition forces the XOR difference between corresponding entries to alternate with the parity of the column.
    501 
    502 **Hint 2**
    503 
    504 We need many values $h$ satisfying
    505 
    506 $ \{0,1,\ldots,n-1\}\mathbin{\operatorname{xor}}h=\{0,1,\ldots,n-1\}. $
    507 
    508 How large is the XOR stabilizer of this set?
    509 
    510 **Hint 3**
    511 
    512 When $n$ is a power of two, pair the values as $y\leftrightarrow y\oplus x$, and place several complete pairs at odd positions.
    513 
    514 **Solution**
    515 
    516 We first determine when a solution can exist. Let $S={0,1,\ldots,n-1}$, and define the XOR difference between adjacent rows in column $j$ by
    517 
    518 $ d_i(j)=A_{i,j}\oplus A_{i+1,j}. $
    519 
    520 The condition on every adjacent $2\times2$ submatrix implies
    521 
    522 $ d_i(j+1)=d_i(j)\oplus x. $
    523 
    524 Thus, once the parity of the column is fixed, the XOR difference between the two rows is fixed. At least $\lceil n/2\rceil$ rows have the same parity, and every column must be a permutation. Therefore, we need at least $\lceil n/2\rceil$ distinct values $h$ such that $S\oplus h=S$.
    525 
    526 Let $L=\operatorname{lowbit}(n)$. The XOR stabilizer of $S$ is exactly
    527 
    528 $ \{0,1,\ldots,L-1\}. $
    529 
    530 Every value smaller than $L$ merely permutes elements within blocks of length $L$. Conversely, write $h=gL+r$, where $0\le r \lt L$. If $g\ne0$, XOR by $h$ induces a nontrivial pairing of the block indices. Since the number of blocks, $n/L$, is odd, the whole set of block indices cannot remain invariant. Hence, $g=0$.
    531 
    532 The necessary condition is therefore
    533 
    534 $ \operatorname{lowbit}(n)\ge\left\lceil\frac n2\right\rceil. $
    535 
    536 This holds only when $n$ is a power of two. In addition, when $n=2$, each value appears twice in any $2\times2$ Latin square, so the XOR of all four entries is always $0$. Thus, no solution exists for $n=2$ and $x \gt 0$.
    537 
    538 We now describe the construction.
    539 
    540 If $x=0$, set
    541 
    542 $ A_{i,j}=i\oplus j. $
    543 
    544 Because $n$ is a power of two, XOR with a fixed value permutes $S$, so every row and every column is a permutation. In each adjacent $2\times2$ submatrix, every index term appears twice, and the total XOR is $0$.
    545 
    546 Now assume $x \gt 0$, $n$ is a power of two, and $n\ge4$. The map $y\mapsto y\oplus x$ partitions $S$ into $n/2$ pairs. Choose $n/4$ of these pairs to form a set $O$, and let the remaining values form a set $E$. Then
    547 
    548 $ |E|=|O|=\frac n2,\qquad E\oplus x=E,\qquad O\oplus x=O. $
    549 
    550 Construct a permutation $p$ by placing the elements of $E$ at even positions and the elements of $O$ at odd positions. Then define
    551 
    552 $ A_{i,j}=p_i\oplus p_j\oplus\bigl((i\bmod2)(j\bmod2)x\bigr). $
    553 
    554 Every even-indexed row is a fixed XOR translation of $p$. In an odd-indexed row, the even columns contain $p_i\oplus E$, while the odd columns contain $p_i\oplus(O\oplus x)=p_i\oplus O$. Together, they still form $S$. The formula is symmetric in $i$ and $j$, so the same argument applies to every column.
    555 
    556 Finally, consider any adjacent $2\times2$ submatrix. The four terms involving $p$ cancel in pairs. Among the four parity pairs, exactly one is $(1,1)$, so the remaining XOR is exactly $x$.
    557 
    558 The output contains $n^2$ numbers, so the time complexity is $O(n^2)$, and the extra space complexity is $O(n)$.
    559 
    560 **Code**
    561 
    562 ```
    563 #include <bits/stdc++.h>
    564 using namespace std;
    565 
    566 const int N = 2500;
    567 
    568 int n, x;
    569 int vis[N + 10], in_o[N + 10], e[N + 10], o[N + 10], a[N + 10];
    570 pair<int, int> p[N + 10];
    571 
    572 bool check(int v) {
    573 	return (v & (v - 1)) == 0;
    574 }
    575 
    576 void work() {
    577 	cin >> n >> x;
    578 
    579 	if (!check(n) || (x && n < 4)) {
    580 		cout << -1 << '\n';
    581 		return;
    582 	}
    583 
    584 	if (!x) {
    585 		for (int i = 0; i < n; ++i) {
    586 			for (int j = 0; j < n; ++j) {
    587 				cout << (i ^ j) << (j + 1 == n ? '\n' : ' ');
    588 			}
    589 		}
    590 		return;
    591 	}
    592 
    593 	for (int i = 0; i <= n; ++i) vis[i] = in_o[i] = e[i] = o[i] = a[i] = 0;
    594 
    595 	int cnt = 0;
    596 	for (int i = 0; i < n; ++i) {
    597 		if (vis[i]) continue;
    598 		int j = i ^ x;
    599 		vis[i] = vis[j] = 1;
    600 		p[++cnt] = {i, j};
    601 	}
    602 
    603 	for (int i = 1; i <= n / 4; ++i) in_o[p[i].first] = in_o[p[i].second] = 1;
    604 
    605 	int ec = 0, oc = 0;
    606 	for (int i = 0; i < n; ++i) {
    607 		if (in_o[i]) o[++oc] = i;
    608 		else e[++ec] = i;
    609 	}
    610 
    611 	ec = oc = 0;
    612 	for (int i = 0; i < n; ++i) {
    613 		if (i & 1) a[i] = o[++oc];
    614 		else a[i] = e[++ec];
    615 	}
    616 
    617 	for (int i = 0; i < n; ++i) {
    618 		for (int j = 0; j < n; ++j) {
    619 			int v = a[i] ^ a[j];
    620 			if ((i & 1) && (j & 1)) v ^= x;
    621 			cout << v << (j + 1 == n ? '\n' : ' ');
    622 		}
    623 	}
    624 }
    625 
    626 int main() {
    627 	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    628 
    629 	int T; cin >> T;
    630 	while (T--) work();
    631 
    632 	return 0;
    633 }
    634 ```
    635 
    636 ## [2249E1 - String (Easy Version)](/contest/2249/problem/E1 "Codeforces Round 1112 (Div. 1)")
    637 
    638 * Idea:[131241](/profile/131241 "Specialist 131241")
    639 * Solution:[131241](/profile/131241 "Specialist 131241")
    640 
    641 **Hint 1**
    642 
    643 Treat a prefix of length $k^i$ as one block. How can it be decomposed into smaller blocks?
    644 
    645 **Hint 2**
    646 
    647 Adding the same value to every character modulo $k$ produces only finitely many translated versions of the pattern-matching problem.
    648 
    649 **Hint 3**
    650 
    651 For each block, store its internal occurrence count and its prefix and suffix of length at most $n-1$. When two blocks are merged, only occurrences crossing their boundary need additional processing.
    652 
    653 **Solution**
    654 
    655 Consider the self-similar structure of the infinite string. Let $B_{i,j}$ denote the standard block of length $k^i$ whose characters are all shifted by $j$ modulo $k$. Then
    656 
    657 $ B_{i,j}=B_{i-1,j}B_{i-1,j+1}\cdots B_{i-1,j+k-1}, $
    658 
    659 where all second indices are taken modulo $k$. This follows directly from how the base-$k$ digit sum changes when the highest digit is increased.
    660 
    661 For the current pattern $t$, maintain the following information for every block:
    662 
    663 * The number of occurrences of $t$ entirely inside the block.
    664 * A prefix of the block of length at most $n-1$.
    665 * A suffix of the block of length at most $n-1$.
    666 
    667 When two adjacent blocks are concatenated, their internal occurrence counts are added. Every newly created occurrence must cross the boundary, so it is sufficient to run KMP on the suffix of the left block followed by the prefix of the right block. The new prefix and suffix are again truncated to at most $n-1$ characters.
    668 
    669 Storing these boundary strings explicitly at every level would still be too slow. Let $x$ be the smallest integer such that $n\le k^x$. Once the block length reaches this scale, every boundary string is a uniform translation of the boundary of a standard block. Therefore, the contribution across the boundary of two large blocks depends only on their two translation values. There are only $k^2$ such pairs, so all of them can be precomputed.
    670 
    671 For a query interval $[l,r]$, recursively decompose it in base $k$ into $O(k\log_k V)$ standard blocks and concatenate them in order. The internal occurrence count of each block is obtained from preprocessing, while occurrences crossing block boundaries are counted using either the stored short boundaries or the precomputed translation transitions.
    672 
    673 At levels where the block length is smaller than $n$, the pattern cannot occur entirely inside a block. The first critical level can be processed directly; at all larger levels, only the finite set of translation transitions is needed. The total time complexity is
    674 
    675 $ O\left(\sum n\cdot k^2+qk^2\log_k V\right), $
    676 
    677 where $V=10^{17}$. The space complexity is $O(n+k^2\log_k V)$.
    678 
    679 **Code**
    680 
    681 ```
    682 #include <bits/stdc++.h>
    683 using namespace std;
    684 
    685 struct node {
    686 	long long v = 0;
    687 	bool b = 0;
    688 	string l = "", r = "";
    689 	int l1, r1;
    690 };
    691 
    692 int n, k;
    693 int fai[2000005];
    694 long long T, ql, qr, trans[10][10];
    695 long long ma, L, R;
    696 node a[66][10], ans;
    697 string pl[10], pr[10], s;
    698 
    699 void make_fai() {
    700 	for (int i = 1; i <= n; ++i) s[i] ^= 48;
    701 
    702 	int l = 0;
    703 	for (int i = 2; i <= n; ++i) {
    704 		while (l && s[l + 1] != s[i]) l = fai[l];
    705 		l += s[l + 1] == s[i];
    706 		fai[i] = l;
    707 	}
    708 }
    709 
    710 int val(string x) {
    711 	int l = 0, res = 0;
    712 
    713 	for (int i = 0; i < (int)x.size(); ++i) {
    714 		while (l && s[l + 1] != x[i]) l = fai[l];
    715 		l += s[l + 1] == x[i];
    716 		if (l == n) ++res;
    717 	}
    718 
    719 	return res;
    720 }
    721 
    722 node add(node &x, node &y) {
    723 	node res;
    724 
    725 	if (x.b && y.b) {
    726 		res.b = 1;
    727 		res.l1 = x.l1;
    728 		res.r1 = y.r1;
    729 		res.v = x.v + y.v + trans[x.r1][y.l1];
    730 		return res;
    731 	}
    732 
    733 	if (x.b) x.l = pl[x.l1], x.r = pr[x.r1];
    734 	if (y.b) y.l = pl[y.l1], y.r = pr[y.r1];
    735 	res.v = x.v + y.v + val(x.r + y.l);
    736 	res.l = x.l;
    737 
    738 	if ((int)res.l.size() < n - 1) {
    739 		int t = min(n - 1 - (int)res.l.size(), (int)y.l.size());
    740 		res.l += y.l.substr(0, t);
    741 	}
    742 
    743 	res.r = y.r;
    744 	if ((int)res.r.size() < n - 1) {
    745 		int t = min(n - 1 - (int)res.r.size(), (int)x.r.size());
    746 		res.r = x.r.substr(x.r.size() - t, t) + res.r;
    747 	}
    748 
    749 	return res;
    750 }
    751 
    752 void init(long long x) {
    753 	bool done = 0;
    754 
    755 	for (long long cur = 1, i = 0; cur <= x; cur *= k, ++i) {
    756 		ma = i;
    757 		L = 0, R = cur;
    758 
    759 		if (i == 0) {
    760 			for (int j = 0; j < k; ++j) {
    761 				if (n == 1) {
    762 					a[0][j].v = j == s[1];
    763 					a[0][j].b = 0;
    764 					a[0][j].l = a[0][j].r = "";
    765 				}
    766 				else {
    767 					a[0][j].v = 0;
    768 					a[0][j].b = 0;
    769 					a[0][j].l = a[0][j].r = "";
    770 					a[0][j].l += (char)j;
    771 					a[0][j].r = a[0][j].l;
    772 				}
    773 			}
    774 		}
    775 		else {
    776 			for (int j = 0; j < k; ++j) {
    777 				node cur;
    778 				for (int t = 0; t < k; ++t) {
    779 					if (!cur.v && !cur.b && cur.l.empty()) cur = a[i - 1][(j + t) % k];
    780 					else cur = add(cur, a[i - 1][(j + t) % k]);
    781 				}
    782 				a[i][j] = cur;
    783 			}
    784 		}
    785 
    786 		if (!done && cur >= n - 1) {
    787 			done = 1;
    788 			for (int j = 0; j < k; ++j) {
    789 				pl[j] = a[i][j].l;
    790 				pr[j] = a[i][j].r;
    791 				a[i][j].b = 1;
    792 				a[i][j].l1 = a[i][j].r1 = j;
    793 				a[i][j].l = a[i][j].r = "";
    794 			}
    795 			for (int j = 0; j < k; ++j) {
    796 				for (int t = 0; t < k; ++t) trans[j][t] = val(pr[j] + pl[t]);
    797 			}
    798 		}
    799 	}
    800 }
    801 
    802 void calc(int dep, int st, long long l, long long r) {
    803 	if (r <= ql || l > qr) return;
    804 
    805 	if (ql <= l && r - 1 <= qr) {
    806 		ans = add(ans, a[dep][st]);
    807 		return;
    808 	}
    809 
    810 	node cur;
    811 	long long len = r - l;
    812 
    813 	for (int i = 0; i < k; ++i) {
    814 		long long nl = l + len / k * i, nr = nl + len / k;
    815 
    816 		if (ql <= nl && nr - 1 <= qr) {
    817 			if (!cur.v && !cur.b && cur.l.empty()) cur = a[dep - 1][(st + i) % k];
    818 			else cur = add(cur, a[dep - 1][(st + i) % k]);
    819 			continue;
    820 		}
    821 
    822 		if (cur.v || cur.b || !cur.l.empty()) {
    823 			ans = add(ans, cur);
    824 			cur.v = 0, cur.b = 0;
    825 			cur.l = cur.r = "";
    826 		}
    827 		calc(dep - 1, (st + i) % k, nl, nr);
    828 	}
    829 
    830 	if (cur.v || cur.b || !cur.l.empty()) ans = add(ans, cur);
    831 }
    832 
    833 int main() {
    834 	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    835 
    836 	cin >> k >> T;
    837 	while (T--) {
    838 		cin >> ql >> qr >> n >> s;
    839 		s = " " + s + "!";
    840 
    841 		make_fai();
    842 		init(qr);
    843 		++ma, R *= k;
    844 
    845 		ans.v = 0, ans.b = 0;
    846 		ans.l = ans.r = "";
    847 		calc(ma, 0, L, R);
    848 		cout << ans.v << '\n';
    849 	}
    850 
    851 	return 0;
    852 }
    853 ```
    854 
    855 ## [2249E2 - String (Hard Version)](/contest/2249/problem/E2 "Codeforces Round 1112 (Div. 1)")
    856 
    857 * Idea:[131241](/profile/131241 "Specialist 131241")
    858 * Solution:[131241](/profile/131241 "Specialist 131241")
    859 
    860 **Hint 1**
    861 
    862 Partition the infinite string into blocks of length $k$. Every block is a cyclic shift of $\mathtt{012\ldots(k-1)}$. If each block is replaced by its shift value, the resulting sequence is the original infinite string again.
    863 
    864 **Hint 2**
    865 
    866 Let
    867 
    868 $ d_i=(t_i-t_{i-1}+k)\bmod k. $
    869 
    870 Inside a complete block, $d_i$ is always $1$. Therefore, all positions with $d_i\ne1$ must have the same residue modulo $k$.
    871 
    872 **Hint 3**
    873 
    874 If the positions with $d_i\ne1$ determine the block boundaries, compress both the pattern and the query interval by a factor of about $k$ and recurse. If no such position exists, an occurring pattern cannot be longer than $2k$.
    875 
    876 **Solution**
    877 
    878 First examine the block structure of the infinite string $s$. Every block of length $k$ is a cyclic shift of
    879 
    880 $ \mathtt{012\ldots(k-1)}. $
    881 
    882 If each complete block is replaced by its shift value, the resulting sequence is again $s$. Therefore, once the pattern $t$ is aligned with these blocks, both the pattern and the query interval can be compressed by a factor of about $k$.
    883 
    884 To determine the alignment, consider the adjacent differences of $t$ modulo $k$:
    885 
    886 $ d_i=(t_i-t_{i-1}+k)\bmod k. $
    887 
    888 Inside a complete cyclic block, every adjacent difference is $1$. Hence, every position with $d_i\ne1$ must correspond to the same type of block boundary, so all such positions must have the same residue modulo $k$. If two different residues occur, the pattern cannot appear.
    889 
    890 If exactly one residue class occurs, the block boundaries are uniquely determined. Split $t$ according to these boundaries, compress each complete block into its shift value, map $[l,r]$ to the corresponding compressed interval according to the two partial end blocks, and recurse.
    891 
    892 It remains to handle the case in which every $d_i=1$, so the block boundaries are not determined. The string $s$ contains no substring longer than $2k$ whose adjacent differences are all $1$. Otherwise, there would be three corresponding terms satisfying $s_i=s_{i+k}=s_{i+2k}$. However, the equality $s_i=s_{i+k}$ requires a particular carry pattern when $i$ is increased by $k$, and the same pattern cannot hold again for $i+k$.
    893 
    894 Therefore, any pattern that occurs must satisfy $n\le2k$. We can enumerate all possible block alignments, reducing the compressed pattern to length at most $2$. When $n\le k$, we must also consider alignments that compress it to a single character. Different alignments correspond to different starting positions in the original string, so they are not counted more than once.
    895 
    896 We are left with occurrence queries for patterns of length $1$ or $2$.
    897 
    898 For a pattern of length $1$, every complete block of length $k$ contains each character exactly once. Only the final partial block of a prefix query needs to be checked directly.
    899 
    900 For a pattern of length $2$, precompute
    901 
    902 $ f_{p,q,x,y}, $
    903 
    904 the number of occurrences of the pair $xy$ in the first $qk^p$ characters. A block at the next level consists of $k$ shifted copies of a smaller block. Their internal contributions are accumulated with the appropriate shifts, and occurrences crossing block boundaries are counted by checking adjacent endpoints. A prefix can be decomposed in base $k$, and an interval answer is obtained by subtracting two prefix answers.
    905 
    906 The total time complexity is
    907 
    908 $ O\left(qk\log_k V+\sum n+k^3\log_k V+k\log_k^2V\right), $
    909 
    910 where $V=10^{17}$.
    911 
    912 **Code**
    913 
    914 ```
    915 #include<bits/stdc++.h>
    916 #define int long long
    917 using namespace std;
    918 int lg;
    919 int q,L,R,n,k,d[10000005],t[100],b[100];
    920 char c[10000005],s[10000005];
    921 struct node{
    922 	int f[65][65];
    923 }sum[65][65];
    924 node merge(node a,node b,int v=1){
    925 	for(int i=0;i<k;i++){
    926 		for(int j=0;j<k;j++){
    927 			a.f[(i+v)%k][(j+v)%k]+=b.f[i][j];
    928 		}
    929 	}
    930 	return a;
    931 }
    932 int calc(int x){
    933 	int sum=0;
    934 	while(x){
    935 		sum+=x%k;
    936 		x=x/k;
    937 	}
    938 	return sum%k;
    939 }
    940 int sp[70];
    941 int gs(int r,int x,int y){
    942     // Count occurrences of the pattern "xy" in the range [0, r].
    943 	r++;
    944 	int cnt=0,xnow=0,ans=0,lowbit=0;
    945 	for(int i=0;i<=lg;i++){
    946 		sp[i]=r%k;r/=k;
    947 	}
    948 	for(int i=lg;i>=0;i--){
    949 		int j=sp[i];
    950 		if(!j) continue;
    951 		ans+=sum[i][j].f[(x+(k-1)*cnt)%k][(y+(k-1)*cnt)%k];
    952 		if(xnow){
    953 			int px=(cnt-1+lowbit*(k-1))%k,py=cnt%k;
    954 			if(px==x&&py==y){
    955 				ans++;
    956 			}
    957 		}
    958 		xnow+=b[i]*j;
    959 		cnt+=j;
    960 		lowbit=i;
    961 	}
    962 	return ans;
    963 }
    964 int gs(int r,int x){
    965     // Count occurrences of the pattern "x" in the range [0, r].
    966 	r++;
    967 	int sum=r/k,pl=r/k*k,y=calc(pl);
    968 	while(pl<r){
    969 		if(y==x){
    970 			sum++;
    971 			break;
    972 		}
    973 		pl++;
    974 		y++;
    975 		y>=k?y-=k:0;
    976 	}
    977 	return sum;
    978 }
    979 void print(char c){
    980 	if(c<10){
    981 		cout<<char(c+'0');
    982 	}else{
    983 		cout<<char(c+'a'-10);
    984 	}
    985 }
    986 int ans=0;
    987 void solve(int l,int r,int n){
    988     // Compute the answer recursively.
    989 	if(l>r){
    990 		return ;
    991 	}
    992 	for(int i=0;i<k;i++){
    993 		t[i]=0;
    994 	}
    995 	if(n<=2){
    996         // For length at most 2, use prefix-count differences directly.
    997 		if(n==2){
    998 			int pl=c[0],pr=c[1];
    999 			int sum=gs(r,pl,pr)-gs(l,pl,pr);
   1000 			ans+=sum;
   1001 			return ;
   1002 		}else{
   1003 			int sum=0;
   1004 			sum=gs(r,c[0])-gs(l-1,c[0]);
   1005 			ans+=sum;
   1006 			return ;
   1007 		}
   1008 	}
   1009 	int cnt=0;
   1010 	for(int i=1;i<n;i++){
   1011 		d[i]=(c[i]-c[i-1]+k)%k;
   1012 		if(d[i]!=1){
   1013 			if(!t[i%k]) cnt++;
   1014 			t[i%k]=1;
   1015 		}
   1016 	}
   1017 	if(cnt>1){
   1018         // If more than one residue occurs, the pattern cannot appear.
   1019 		return ;
   1020 	}
   1021 	int m=0,pl=k,pr=k,p=0;
   1022 	if(cnt){
   1023         // At least one adjacent difference is not 1.
   1024 		for(int i=1;i<n;i++){
   1025 			if(d[i]!=1) p=i%k;
   1026 		}
   1027 		if(p){
   1028 			pl=p;
   1029 			s[m++]=(c[p-1]+1)%k;
   1030 		}
   1031 		for(int i=p;i<n;i+=k){
   1032 			if(i+k-1>=n) pr=n-i;
   1033 			s[m++]=c[i];
   1034 		}
   1035 
   1036         // Handle the two partial boundary blocks separately.
   1037 		int bl=(r/k)*k,br=(l/k+1)*k-1;
   1038 		if(br-l+1<pl) l=l/k+1;
   1039 		else l=l/k;
   1040 		if(r-bl+1<pr) r=r/k-1;
   1041 		else r=r/k;
   1042 
   1043 		for(int i=0;i<m;i++) c[i]=s[i];
   1044 		solve(l,r,m);
   1045 	}else{
   1046         // Every adjacent difference is 1.
   1047 		int szl=(l/k+1)*k-l,szr=r-(r/k)*k+1,L,R;
   1048 		if(n<=k){
   1049 			int x=c[0];
   1050 			for(int i=0;i+n-1<k;i++){
   1051 				c[0]=(x-i+k)%k;
   1052                 // Handle the two partial boundary blocks separately.
   1053 				pl=k-i,pr=i+n;
   1054 				if(szl<pl) L=l/k+1;
   1055 				else L=l/k;
   1056 				if(szr<pr) R=r/k-1;
   1057 				else R=r/k;
   1058 				solve(L,R,1);
   1059 			}
   1060 		}
   1061 		for(int i=0;i<n;i++){
   1062 			s[i]=c[i];
   1063 		}
   1064 		for(int i=0;i<min(n-1,k);i++){
   1065             // Handle the two partial boundary blocks separately.
   1066 			pl=i+1,pr=n-1-i;
   1067 			if(pr>k) continue;
   1068 			if(szl<pl) L=l/k+1;
   1069 			else L=l/k;
   1070 			if(szr<pr) R=r/k-1;
   1071 			else R=r/k;
   1072 			c[0]=c[1]=s[i+1];
   1073 			solve(L,R,2);
   1074 		}
   1075 	}
   1076 }
   1077 char change(int x){
   1078     if(0<=x&&x<=9) return x+'0';
   1079     if(10<=x&&x<=35) return x-10+'A';
   1080     if(36<=x&&x<=61) return x-36+'a';
   1081 }
   1082 int change(char x){
   1083     if('0'<=x&&x<='9') return x-'0';
   1084     if('A'<=x&&x<='Z') return x+10-'A';
   1085     if('a'<=x&&x<='z') return x+36-'a';
   1086 }
   1087 signed main(){
   1088 	ios::sync_with_stdio(0);
   1089 	cin.tie(0);cout.tie(0);
   1090 	cin>>k>>q;
   1091 
   1092     // sum[i][j] stores counts of length-2 substrings in the first j * k^i characters.
   1093 	b[0]=1;lg=0;
   1094 	for(int i=1;i<=k;i++){
   1095 		for(int j=1;j<i;j++){
   1096 			sum[0][i].f[j-1][j]=1;
   1097 		}
   1098 	}
   1099 	for(int p=1;p;p++){
   1100 		b[p]=b[p-1]*k;
   1101 		lg++;
   1102 		if(b[p]>1e17){
   1103 			break;
   1104 		}
   1105 		sum[p][1]=sum[p-1][k];
   1106         // Concatenate the k shifted blocks.
   1107 		for(int i=2;i<=k;i++){
   1108 			sum[p][i]=merge(sum[p][i-1],sum[p-1][k],i-1);
   1109 			// Count substrings that cross a block boundary directly.
   1110 			sum[p][i].f[calc(b[p]*(i-1)-1)][calc(b[p]*(i-1))]++;
   1111 		}
   1112 	}
   1113 
   1114 	while(q--){
   1115 		cin>>L>>R>>n;
   1116 		cin>>c;
   1117 		for(int i=0;i<n;i++){
   1118 			c[i]=change(c[i]);
   1119 		}
   1120 		solve(L,R,n);
   1121 		cout<<ans<<endl;
   1122 		ans=0;
   1123 	}
   1124     return 0;
   1125 }
   1126 ```
   1127 
   1128 ## [2249F - Even Simple Path](/contest/2249/problem/F "Codeforces Round 1112 (Div. 1)")
   1129 
   1130 * Idea:[aaa_Pigeon2](/profile/aaa_Pigeon2 "International Grandmaster aaa_Pigeon2")
   1131 * Solution:[aaa_Pigeon2](/profile/aaa_Pigeon2 "International Grandmaster aaa_Pigeon2")
   1132 
   1133 **Hint 1**
   1134 
   1135 In a simple path, the two endpoints have degree $1$, every other used vertex has degree $2$, and every unused vertex has degree $0$. Can this degree condition be encoded by a matching?
   1136 
   1137 **Hint 2**
   1138 
   1139 Split every vertex into left and right copies, but remove $R(1)$ and $L(n)$. Original edges connect copies within the same layer, while an unused internal vertex matches its two copies with a cross-layer edge.
   1140 
   1141 **Hint 3**
   1142 
   1143 Give every cross-layer edge weight $M$ and every same-layer edge corresponding to an original edge weight $M-1$. A maximum-weight matching eliminates extra cycles and minimizes the resulting path length.
   1144 
   1145 **Solution**
   1146 
   1147 The main difficulty is the word ``simple''. A shortest path algorithm cannot directly handle the condition that no vertex may be visited twice, so we encode the path as a matching.
   1148 
   1149 First, consider the degree pattern of a simple path from vertex $1$ to vertex $n$:
   1150 
   1151 * vertices $1$ and $n$ have degree $1$ in the path;
   1152 * every other used vertex has degree $2$;
   1153 * every unused vertex has degree $0$.
   1154 
   1155 We will build an auxiliary graph where:
   1156 
   1157 * an unused vertex corresponds to one internal matching edge;
   1158 * a used internal vertex must match both of its copies to other vertices;
   1159 * vertices $1$ and $n$ have only one copy each, so they contribute exactly one path edge.
   1160 
   1161 Then a perfect matching in the auxiliary graph will describe a path in the original graph.
   1162 
   1163 ---
   1164 
   1165 Let the original graph be $G=(V,E)$.
   1166 
   1167 For every vertex $v$, create two copies $L(v)$ and $R(v)$. Then delete $R(1)$ and $L(n)$. Thus the vertex set of the auxiliary graph $G'=(V',E')$ is
   1168 
   1169 $ V'=\{L(v)\mid v\ne n\}\cup\{R(v)\mid v\ne 1\} $
   1170 
   1171 We delete these two copies because vertices $1$ and $n$ should have degree $1$ in the restored path. Every internal vertex still has both copies, so it may contribute degree $2$.
   1172 
   1173 Also, the deleted copies are in different layers. This is what forces the restored path to have even length.
   1174 
   1175 For every original edge $(u,v)\in E$, add the same-layer edges $(L(u),L(v))$ and $(R(u),R(v))$ whenever both endpoints exist. Give each of these edges weight $M-1$.
   1176 
   1177 For every internal vertex $v\notin{1,n}$, add the cross-layer edge $(L(v),R(v))$ with weight $M$.
   1178 
   1179 Here $M$ is a sufficiently large constant, for example any $M \gt |V'|$.
   1180 
   1181 Now find a maximum-weight matching in the general graph $G'$. If it is not a perfect matching, then there is no valid path. Otherwise, we restore the answer from it.
   1182 
   1183 The choice $M \gt |V'|$ is useful here: if a perfect matching exists, any matching that misses at least one edge loses more weight than it can gain by changing all remaining edges from weight $M-1$ to weight $M$. Therefore a maximum-weight matching will be perfect whenever a perfect matching exists.
   1184 
   1185 ---
   1186 
   1187 ## Meaning of a Perfect Matching
   1188 
   1189 Consider a perfect matching $S$ of $G'$.
   1190 
   1191 For an internal vertex $v\notin{1,n}$, both $L(v)$ and $R(v)$ must be matched.
   1192 
   1193 If $S$ contains the cross-layer edge $(L(v),R(v))$, we treat $v$ as unused. This corresponds to degree $0$ in the original graph.
   1194 
   1195 Otherwise, $L(v)$ and $R(v)$ are each matched to another copy through same-layer edges. After mapping these same-layer edges back to the original graph, vertex $v$ has degree $2$.
   1196 
   1197 Vertices $1$ and $n$ have only one copy each and have no cross-layer edge, so they naturally have degree $1$.
   1198 
   1199 Thus the selected same-layer edges map to a subgraph of the original graph in which:
   1200 
   1201 * vertices $1$ and $n$ have degree $1$;
   1202 * every other vertex has degree $0$ or $2$.
   1203 
   1204 So this subgraph consists of one path from $1$ to $n$ and possibly several cycles.
   1205 
   1206 We now prove the construction in both directions and then explain why maximum weight removes the cycles and minimizes the path length.
   1207 
   1208 ---
   1209 
   1210 ### Proof 1: Every Even Simple Path Gives a Perfect Matching
   1211 
   1212 Suppose we have an even-length simple path
   1213 
   1214 $ p_0=1,p_1,p_2,\ldots,p_L=n $
   1215 
   1216 where $2\mid L$.
   1217 
   1218 Choose edges along this path alternately:
   1219 
   1220 * for the first edge $(p_0,p_1)$, choose $(L(p_0),L(p_1))$;
   1221 * for the second edge $(p_1,p_2)$, choose $(R(p_1),R(p_2))$;
   1222 * for the third edge, choose the corresponding left-layer edge;
   1223 * for the fourth edge, choose the corresponding right-layer edge;
   1224 * and so on.
   1225 
   1226 Since $L$ is even, the last path edge $(p_{L-1},p_L)$ is chosen in the right layer, and $R(n)$ exists.
   1227 
   1228 For every internal vertex $v$ not on the path, choose the cross-layer edge $(L(v),R(v))$.
   1229 
   1230 Now every vertex of $G'$ is matched exactly once, so we have constructed a perfect matching.
   1231 
   1232 ---
   1233 
   1234 ### Proof 2: Every Perfect Matching Gives an Even Simple Path
   1235 
   1236 Take any perfect matching of $G'$ and map all selected same-layer edges back to the original graph.
   1237 
   1238 As shown above, the resulting subgraph has degree $1$ at vertices $1$ and $n$, and degree $0$ or $2$ at every other vertex. Therefore it is the disjoint union of one path from $1$ to $n$ and some cycles.
   1239 
   1240 Let us look at the path component. In the auxiliary graph, the endpoint corresponding to vertex $1$ is $L(1)$, while the endpoint corresponding to vertex $n$ is $R(n)$. Along the restored component, same-layer edges are the original graph edges, and the only way to switch layers is through cross-layer edges of the form $(L(v),R(v))$.
   1241 
   1242 Therefore the original edges on the path must appear as
   1243 
   1244 $ \text{left layer},\ \text{right layer},\ \text{left layer},\ \text{right layer},\ldots,\ \text{right layer} $
   1245 
   1246 So the number of original edges on this path is even.
   1247 
   1248 The path component has exactly two vertices of degree $1$ and all other vertices of degree $2$, so it is a simple path. Hence every perfect matching gives an even-length simple path from $1$ to $n$, possibly together with extra cycles.
   1249 
   1250 ---
   1251 
   1252 ### Proof 3: A Maximum-Weight Perfect Matching Has No Extra Cycles
   1253 
   1254 Assume that a maximum-weight perfect matching maps back to a path from $1$ to $n$ plus at least one cycle. Let this cycle contain $k$ vertices.
   1255 
   1256 Every vertex on the cycle is used, so none of them uses its cross-layer edge. The cycle contributes exactly $k$ same-layer matching edges, with total weight
   1257 
   1258 $ k(M-1) $
   1259 
   1260 Now remove this cycle from the matching and, for every vertex $v$ on the cycle, choose the cross-layer edge $(L(v),R(v))$ instead.
   1261 
   1262 This is still a valid perfect matching. The affected part now has total weight
   1263 
   1264 $ kM $
   1265 
   1266 Since $kM \gt k(M-1)$, the matching weight increases, which contradicts maximality.
   1267 
   1268 Therefore a maximum-weight perfect matching cannot produce extra cycles. It restores exactly one even-length simple path from $1$ to $n$.
   1269 
   1270 ---
   1271 
   1272 ### Proof 4: The Restored Path Is Shortest
   1273 
   1274 In any perfect matching of $G'$, the number of matched edges is fixed.
   1275 
   1276 Cross-layer edges have weight $M$, and same-layer edges have weight $M-1$. Thus maximizing the total weight is the same as minimizing the number of selected same-layer edges.
   1277 
   1278 After Proof 3, a maximum-weight perfect matching has no extra cycles, so its selected same-layer edges are exactly the edges of the restored path. Therefore the maximum-weight perfect matching gives a shortest even-length simple path.
   1279 
   1280 ---
   1281 
   1282 ## Finding the Matching and Restoring the Path
   1283 
   1284 The auxiliary graph is not necessarily bipartite, because both the left layer and the right layer may contain edges. Therefore we need maximum-weight matching in a general graph, for example the weighted blossom algorithm.
   1285 
   1286 The auxiliary graph has $2n-2$ vertices and at most $2m+n-2$ edges. The weighted blossom algorithm runs in $O(|V'|^3)$ time.
   1287 
   1288 After computing the maximum-weight matching:
   1289 
   1290 * if its size is not $|V'|/2$, output $-1$;
   1291 * otherwise, take the symmetric difference between the matching edges and all cross-layer edges $(L(v),R(v))$ for $v\notin{1,n}$.
   1292 
   1293 Unused vertices disappear from this symmetric difference, because their cross-layer edge is present in both sets. Used vertices remain connected through their two copies.
   1294 
   1295 The resulting auxiliary graph contains one path from $L(1)$ to $R(n)$ and no cycles for a maximum-weight matching. Traverse this path and write down the original vertex whenever a same-layer edge is crossed. This gives the required shortest even-length simple path from vertex $1$ to vertex $n$.
   1296 
   1297 **Code**
   1298 
   1299 ```
   1300 #include <bits/stdc++.h>
   1301 using namespace std;
   1302 
   1303 const int N = 1000;
   1304 const int V = 2 * N;
   1305 const int B = 2 * V;
   1306 const int inf = 0x3f3f3f3f;
   1307 const int big = 10000;
   1308 
   1309 struct edge {
   1310 	int u, v, w;
   1311 };
   1312 
   1313 int n, m;
   1314 int idL[N + 10], idR[N + 10], ori[V + 10];
   1315 int init_u[N + 10], init_v[N + 10], init_cnt;
   1316 char sx[V + 10][V + 10];
   1317 vector<int> adj[V + 10];
   1318 
   1319 struct blossom_tree {
   1320 	int n, nx;
   1321 	edge g[B + 10][B + 10];
   1322 	int lab[B + 10], match[B + 10], slack[B + 10], st[B + 10], pa[B + 10];
   1323 	int flower_from[B + 10][V + 10], flower[B + 10][V + 10];
   1324 	int S[B + 10], vis[B + 10], flower_cnt[B + 10], tmp[V + 10];
   1325 	queue<int> q;
   1326 
   1327 	void init(int _n) {
   1328 		n = _n, nx = n;
   1329 
   1330 		for (int i = 0; i <= 2 * n + 2; ++i) {
   1331 			lab[i] = match[i] = slack[i] = st[i] = pa[i] = S[i] = vis[i] = 0;
   1332 			flower_cnt[i] = 0;
   1333 			for (int j = 0; j <= n; ++j) flower_from[i][j] = 0;
   1334 		}
   1335 
   1336 		for (int i = 1; i <= 2 * n + 2; ++i) {
   1337 			for (int j = 1; j <= 2 * n + 2; ++j) g[i][j] = {i, j, 0};
   1338 		}
   1339 	}
   1340 
   1341 	void add_edge(int u, int v, int w) {
   1342 		if (u == v) return;
   1343 
   1344 		if (w > g[u][v].w) {
   1345 			g[u][v] = {u, v, w};
   1346 			g[v][u] = {v, u, w};
   1347 		}
   1348 	}
   1349 
   1350 	int e_delta(edge e) {
   1351 		return lab[e.u] + lab[e.v] - g[e.u][e.v].w * 2;
   1352 	}
   1353 
   1354 	void update_slack(int u, int x) {
   1355 		if (!slack[x] || e_delta(g[u][x]) < e_delta(g[slack[x]][x])) slack[x] = u;
   1356 	}
   1357 
   1358 	void set_slack(int x) {
   1359 		slack[x] = 0;
   1360 
   1361 		for (int u = 1; u <= n; ++u) {
   1362 			if (g[u][x].w && st[u] != x && S[st[u]] == 0) update_slack(u, x);
   1363 		}
   1364 	}
   1365 
   1366 	void q_push(int x) {
   1367 		if (x <= n) q.push(x);
   1368 		else {
   1369 			for (int i = 0; i < flower_cnt[x]; ++i) q_push(flower[x][i]);
   1370 		}
   1371 	}
   1372 
   1373 	void set_st(int x, int b) {
   1374 		st[x] = b;
   1375 
   1376 		if (x > n) {
   1377 			for (int i = 0; i < flower_cnt[x]; ++i) set_st(flower[x][i], b);
   1378 		}
   1379 	}
   1380 
   1381 	void reverse_flower(int b, int l, int r) {
   1382 		while (l < r) {
   1383 			swap(flower[b][l], flower[b][r]);
   1384 			++l, --r;
   1385 		}
   1386 	}
   1387 
   1388 	void rotate_flower(int b, int pr) {
   1389 		int cnt = flower_cnt[b];
   1390 
   1391 		for (int i = 0; i < cnt; ++i) tmp[i] = flower[b][(i + pr) % cnt];
   1392 		for (int i = 0; i < cnt; ++i) flower[b][i] = tmp[i];
   1393 	}
   1394 
   1395 	int get_pr(int b, int xr) {
   1396 		int pr = 0;
   1397 
   1398 		while (flower[b][pr] != xr) ++pr;
   1399 
   1400 		if (pr & 1) {
   1401 			reverse_flower(b, 1, flower_cnt[b] - 1);
   1402 			return flower_cnt[b] - pr;
   1403 		}
   1404 
   1405 		return pr;
   1406 	}
   1407 
   1408 	void set_match(int u, int v) {
   1409 		match[u] = g[u][v].v;
   1410 
   1411 		if (u > n) {
   1412 			edge e = g[u][v];
   1413 			int xr = flower_from[u][e.u];
   1414 			int pr = get_pr(u, xr);
   1415 
   1416 			for (int i = 0; i < pr; ++i) set_match(flower[u][i], flower[u][i ^ 1]);
   1417 
   1418 			set_match(xr, v);
   1419 			rotate_flower(u, pr);
   1420 		}
   1421 	}
   1422 
   1423 	void augment(int u, int v) {
   1424 		while (true) {
   1425 			int xnv = st[match[u]];
   1426 
   1427 			set_match(u, v);
   1428 
   1429 			if (!xnv) return;
   1430 
   1431 			set_match(xnv, st[pa[xnv]]);
   1432 			u = st[pa[xnv]], v = xnv;
   1433 		}
   1434 	}
   1435 
   1436 	int get_lca(int u, int v) {
   1437 		static int tim = 0;
   1438 		++tim;
   1439 
   1440 		while (u || v) {
   1441 			if (u) {
   1442 				if (vis[u] == tim) return u;
   1443 
   1444 				vis[u] = tim;
   1445 				u = st[match[u]];
   1446 
   1447 				if (u) u = st[pa[u]];
   1448 			}
   1449 
   1450 			swap(u, v);
   1451 		}
   1452 
   1453 		return 0;
   1454 	}
   1455 
   1456 	void add_blossom(int u, int lca, int v) {
   1457 		int b = n + 1;
   1458 
   1459 		while (b <= nx && st[b]) ++b;
   1460 		if (b > nx) ++nx;
   1461 
   1462 		lab[b] = 0, S[b] = 0, match[b] = match[lca];
   1463 		flower_cnt[b] = 0;
   1464 		flower[b][flower_cnt[b]++] = lca;
   1465 
   1466 		for (int x = u, y; x != lca; x = st[pa[y]]) {
   1467 			flower[b][flower_cnt[b]++] = x;
   1468 			y = st[match[x]];
   1469 			flower[b][flower_cnt[b]++] = y;
   1470 			q_push(y);
   1471 		}
   1472 
   1473 		reverse_flower(b, 1, flower_cnt[b] - 1);
   1474 
   1475 		for (int x = v, y; x != lca; x = st[pa[y]]) {
   1476 			flower[b][flower_cnt[b]++] = x;
   1477 			y = st[match[x]];
   1478 			flower[b][flower_cnt[b]++] = y;
   1479 			q_push(y);
   1480 		}
   1481 
   1482 		set_st(b, b);
   1483 
   1484 		for (int x = 1; x <= nx; ++x) {
   1485 			g[b][x] = {b, x, 0};
   1486 			g[x][b] = {x, b, 0};
   1487 		}
   1488 
   1489 		for (int x = 1; x <= n; ++x) flower_from[b][x] = 0;
   1490 
   1491 		for (int i = 0; i < flower_cnt[b]; ++i) {
   1492 			int xs = flower[b][i];
   1493 
   1494 			for (int x = 1; x <= nx; ++x) {
   1495 				if (g[xs][x].w && (!g[b][x].w || e_delta(g[xs][x]) < e_delta(g[b][x]))) {
   1496 					g[b][x] = g[xs][x];
   1497 					g[x][b] = g[x][xs];
   1498 				}
   1499 			}
   1500 
   1501 			for (int x = 1; x <= n; ++x) {
   1502 				if (flower_from[xs][x]) flower_from[b][x] = xs;
   1503 			}
   1504 		}
   1505 
   1506 		set_slack(b);
   1507 	}
   1508 
   1509 	void expand_blossom(int b) {
   1510 		for (int i = 0; i < flower_cnt[b]; ++i) set_st(flower[b][i], flower[b][i]);
   1511 
   1512 		int xr = flower_from[b][g[b][pa[b]].u];
   1513 		int pr = get_pr(b, xr);
   1514 
   1515 		for (int i = 0; i < pr; i += 2) {
   1516 			int xs = flower[b][i];
   1517 			int xns = flower[b][i + 1];
   1518 
   1519 			pa[xs] = g[xns][xs].u;
   1520 			S[xs] = 1, S[xns] = 0;
   1521 			slack[xs] = 0;
   1522 
   1523 			set_slack(xns);
   1524 			q_push(xns);
   1525 		}
   1526 
   1527 		S[xr] = 1;
   1528 		pa[xr] = pa[b];
   1529 
   1530 		for (int i = pr + 1; i < flower_cnt[b]; ++i) {
   1531 			int xs = flower[b][i];
   1532 
   1533 			S[xs] = -1;
   1534 			set_slack(xs);
   1535 		}
   1536 
   1537 		st[b] = 0;
   1538 	}
   1539 
   1540 	bool on_found_edge(edge e) {
   1541 		int u = st[e.u], v = st[e.v];
   1542 
   1543 		if (S[v] == -1) {
   1544 			pa[v] = e.u;
   1545 			S[v] = 1;
   1546 
   1547 			int nu = st[match[v]];
   1548 
   1549 			slack[v] = slack[nu] = 0;
   1550 			S[nu] = 0;
   1551 
   1552 			q_push(nu);
   1553 		}
   1554 		else if (S[v] == 0) {
   1555 			int lca = get_lca(u, v);
   1556 
   1557 			if (!lca) {
   1558 				augment(u, v);
   1559 				augment(v, u);
   1560 				return true;
   1561 			}
   1562 			else add_blossom(u, lca, v);
   1563 		}
   1564 
   1565 		return false;
   1566 	}
   1567 
   1568 	bool matching() {
   1569 		for (int i = 1; i <= nx; ++i) S[i] = -1, slack[i] = 0;
   1570 
   1571 		while (!q.empty()) q.pop();
   1572 
   1573 		for (int x = 1; x <= nx; ++x) {
   1574 			if (st[x] == x && !match[x]) {
   1575 				pa[x] = 0;
   1576 				S[x] = 0;
   1577 				q_push(x);
   1578 			}
   1579 		}
   1580 
   1581 		if (q.empty()) return false;
   1582 
   1583 		while (true) {
   1584 			while (!q.empty()) {
   1585 				int u = q.front(); q.pop();
   1586 				if (S[st[u]] == 1) continue;
   1587 
   1588 				for (int v = 1; v <= n; ++v) {
   1589 					if (g[u][v].w && st[u] != st[v]) {
   1590 						if (!e_delta(g[u][v])) {
   1591 							if (on_found_edge(g[u][v])) return true;
   1592 						}
   1593 						else update_slack(u, st[v]);
   1594 					}
   1595 				}
   1596 			}
   1597 
   1598 			int d = inf;
   1599 
   1600 			for (int u = 1; u <= n; ++u) {
   1601 				if (S[st[u]] == 0) d = min(d, lab[u]);
   1602 			}
   1603 
   1604 			for (int b = n + 1; b <= nx; ++b) {
   1605 				if (st[b] == b && S[b] == 1) d = min(d, lab[b] / 2);
   1606 			}
   1607 
   1608 			for (int x = 1; x <= nx; ++x) {
   1609 				if (st[x] == x && slack[x]) {
   1610 					if (S[x] == -1) d = min(d, e_delta(g[slack[x]][x]));
   1611 					else if (S[x] == 0) d = min(d, e_delta(g[slack[x]][x]) / 2);
   1612 				}
   1613 			}
   1614 
   1615 			if (d == inf) return false;
   1616 
   1617 			for (int u = 1; u <= n; ++u) {
   1618 				if (S[st[u]] == 0) {
   1619 					if (lab[u] == d) return false;
   1620 					lab[u] -= d;
   1621 				}
   1622 				else if (S[st[u]] == 1) lab[u] += d;
   1623 			}
   1624 
   1625 			for (int b = n + 1; b <= nx; ++b) {
   1626 				if (st[b] == b) {
   1627 					if (S[b] == 0) lab[b] += d * 2;
   1628 					else if (S[b] == 1) lab[b] -= d * 2;
   1629 				}
   1630 			}
   1631 
   1632 			while (!q.empty()) q.pop();
   1633 
   1634 			for (int x = 1; x <= nx; ++x) {
   1635 				if (st[x] == x && slack[x] && st[slack[x]] != x && !e_delta(g[slack[x]][x])) {
   1636 					if (on_found_edge(g[slack[x]][x])) return true;
   1637 				}
   1638 			}
   1639 
   1640 			for (int b = n + 1; b <= nx; ++b) {
   1641 				if (st[b] == b && S[b] == 1 && !lab[b]) expand_blossom(b);
   1642 			}
   1643 		}
   1644 	}
   1645 
   1646 	int solve() {
   1647 		nx = n;
   1648 		int cnt = 0, mx = 0;
   1649 
   1650 		for (int i = 0; i <= 2 * n + 2; ++i) {
   1651 			lab[i] = match[i] = slack[i] = pa[i] = S[i] = vis[i] = 0;
   1652 			st[i] = 0;
   1653 			flower_cnt[i] = 0;
   1654 		}
   1655 
   1656 		for (int i = 0; i <= n; ++i) st[i] = i;
   1657 
   1658 		for (int u = 1; u <= n; ++u) {
   1659 			for (int v = 1; v <= n; ++v) {
   1660 				flower_from[u][v] = (u == v ? u : 0);
   1661 				mx = max(mx, g[u][v].w);
   1662 			}
   1663 		}
   1664 
   1665 		for (int u = 1; u <= n; ++u) lab[u] = mx;
   1666 
   1667 		while (matching()) ++cnt;
   1668 		return cnt;
   1669 	}
   1670 } blossom;
   1671 
   1672 int new_node(int x, int &tot) {
   1673 	ori[tot + 1] = x;
   1674 	return ++tot;
   1675 }
   1676 
   1677 void toggle_edge(int u, int v) {
   1678 	if (u > v) swap(u, v);
   1679 	sx[u][v] ^= 1;
   1680 }
   1681 
   1682 void work() {
   1683 	cin >> n >> m;
   1684 
   1685 	memset(idL, -1, sizeof(idL));
   1686 	memset(idR, -1, sizeof(idR));
   1687 
   1688 	int tot = 0;
   1689 
   1690 	for (int i = 1; i <= n; ++i) {
   1691 		if (i != n) idL[i] = new_node(i, tot);
   1692 	}
   1693 	for (int i = 1; i <= n; ++i) {
   1694 		if (i != 1) idR[i] = new_node(i, tot);
   1695 	}
   1696 
   1697 	blossom.init(tot);
   1698 
   1699 	for (int i = 1; i <= m; ++i) {
   1700 		int u, v; cin >> u >> v;
   1701 
   1702 		if (idL[u] != -1 && idL[v] != -1) blossom.add_edge(idL[u], idL[v], big - 1);
   1703 		if (idR[u] != -1 && idR[v] != -1) blossom.add_edge(idR[u], idR[v], big - 1);
   1704 	}
   1705 
   1706 	init_cnt = 0;
   1707 
   1708 	for (int i = 2; i < n; ++i) {
   1709 		blossom.add_edge(idL[i], idR[i], big);
   1710 		init_u[++init_cnt] = idL[i], init_v[init_cnt] = idR[i];
   1711 	}
   1712 
   1713 	int cnt = blossom.solve();
   1714 
   1715 	if (cnt != tot / 2) {
   1716 		cout << -1 << '\n';
   1717 		return;
   1718 	}
   1719 
   1720 	for (int i = 1; i <= tot; ++i) {
   1721 		adj[i].clear();
   1722 		for (int j = 1; j <= tot; ++j) sx[i][j] = 0;
   1723 	}
   1724 
   1725 	for (int i = 1; i <= tot; ++i) {
   1726 		if (blossom.match[i] && i < blossom.match[i]) toggle_edge(i, blossom.match[i]);
   1727 	}
   1728 
   1729 	for (int i = 1; i <= init_cnt; ++i) toggle_edge(init_u[i], init_v[i]);
   1730 
   1731 	for (int i = 1; i <= tot; ++i) {
   1732 		for (int j = i + 1; j <= tot; ++j) {
   1733 			if (sx[i][j]) {
   1734 				adj[i].push_back(j);
   1735 				adj[j].push_back(i);
   1736 			}
   1737 		}
   1738 	}
   1739 
   1740 	int st = idL[1], ed = idR[n];
   1741 	vector<int> aux, path;
   1742 	int last = 0, cur = st;
   1743 
   1744 	while (true) {
   1745 		aux.push_back(cur);
   1746 		if (cur == ed) break;
   1747 
   1748 		int nxt = 0;
   1749 
   1750 		for (int v : adj[cur]) {
   1751 			if (v != last) {
   1752 				nxt = v;
   1753 				break;
   1754 			}
   1755 		}
   1756 
   1757 		if (!nxt) {
   1758 			cout << -1 << '\n';
   1759 			return;
   1760 		}
   1761 
   1762 		last = cur, cur = nxt;
   1763 
   1764 		if ((int)aux.size() > tot + 5) {
   1765 			cout << -1 << '\n';
   1766 			return;
   1767 		}
   1768 	}
   1769 
   1770 	path.push_back(1);
   1771 	for (int i = 1; i < (int)aux.size(); ++i) {
   1772 		int u = aux[i - 1], v = aux[i];
   1773 		if (ori[u] != ori[v]) path.push_back(ori[v]);
   1774 	}
   1775 
   1776 	if (path.back() != n || ((int)path.size() - 1) % 2) {
   1777 		cout << -1 << '\n';
   1778 		return;
   1779 	}
   1780 
   1781 	cout << (int)path.size() - 1 << '\n';
   1782 	for (int i = 0; i < (int)path.size(); ++i) {
   1783 		if (i) cout << ' ';
   1784 		cout << path[i];
   1785 	}
   1786 	cout << '\n';
   1787 }
   1788 
   1789 int main() {
   1790 	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
   1791 
   1792 	int T; cin >> T;
   1793 	while (T--) work();
   1794 
   1795 	return 0;
   1796 }
   1797 ```