Let us determine what is required for every position to contain exactly one element after the simultaneous move.

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$$$.

Thus, the elements at positions $$$1$$$ and $$$2$$$ must swap. Repeating the same argument for the remaining positions, the only possible movement pattern is

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.

Let

We need an integer $$$k$$$ such that $$$L \lt k \lt R$$$. Such an integer exists if and only if $$$L+2\le R$$$.

The time complexity is $$$O(n)$$$ per test case, and the extra space complexity is $$$O(1)$$$.

#include <bits/stdc++.h>
using namespace std;

void work() {
	int n; cin >> n;
	long long L = 0, R = 1000000001LL;

	for (int i = 1; i <= n; ++i) {
		long long w; cin >> w;
		if (i & 1) R = min(R, w);
		else L = max(L, w);
	}

	cout << (n % 2 == 0 && L + 2 <= R ? "YES" : "NO") << '\n';
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int T; cin >> T;
	while (T--) work();

	return 0;
}

Partition the string into maximal blocks of equal characters. How does the number of blocks determine the number of adjacent equal pairs?

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

Therefore, we need to construct a string with exactly $$$r=n-k$$$ blocks.

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.

Now assume $$$r\ge2$$$. Let the block characters alternate, starting with $$$\mathtt{0}$$$. The numbers of $$$\mathtt{0}$$$-blocks and $$$\mathtt{1}$$$-blocks are

We want the total numbers of the two characters to be

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$$$.

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.

The time complexity is $$$O(n)$$$ per test case and $$$O(\sum n)$$$ in total. The space complexity is $$$O(n)$$$.

#include <bits/stdc++.h>
using namespace std;

void work() {
	int n, k; cin >> n >> k;

	if (n > 1 && k == n - 1) {
		cout << -1 << '\n';
		return;
	}

	k = n - k;
	int c0 = (n + 1) / 2, c1 = n / 2;

	for (int i = 1; i <= k; ++i) {
		if (i & 1) {
			if (i + 2 > k) {
				while (c0--) cout << 0;
			}
			else {
				--c0;
				cout << 0;
			}
		}
		else {
			if (i + 2 > k) {
				while (c1--) cout << 1;
			}
			else {
				--c1;
				cout << 1;
			}
		}
	}
	cout << '\n';
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int T; cin >> T;
	while (T--) work();

	return 0;
}

An element's rank from the right depends on both its position in the retained subsequence and the subsequence's final length.

Enumerate the final retained length $$$m$$$. Once $$$m$$$ is fixed, the condition for every position in the subsequence is fixed.

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$$$.

Therefore, we enumerate the final length $$$m$$$.

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

and

Whenever the current element satisfies both conditions, choose it immediately.

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.

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$$$.

The time complexity is $$$O(n^2)$$$ per test case, and the space complexity is $$$O(n)$$$.

#include <bits/stdc++.h>
using namespace std;

const int N = 5000;

int n;
int l[N + 10], r[N + 10], u[N + 10], v[N + 10];

bool check(int m) {
	int j = 1;

	for (int i = 1; i <= n && j <= m; ++i) {
		int x = m - j + 1;
		if ((j < l[i] || j > r[i]) && (x < u[i] || x > v[i])) ++j;
	}

	return j == m + 1;
}

void work() {
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> l[i] >> r[i] >> u[i] >> v[i];

	for (int m = n; m >= 1; --m) {
		if (!check(m)) continue;
		cout << m << '\n';
		return;
	}

	cout << 0 << '\n';
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int T; cin >> T;
	while (T--) work();

	return 0;
}

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.

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.

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.

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$$$.

Now consider the position of $$$n$$$. For cut $$$i$$$:

• If $$$n$$$ lies on the right, then $$$a_i$$$ is the maximum of the prefix on the left.
• If $$$n$$$ lies on the left, then $$$a_i$$$ is the maximum of the suffix on the right.

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.

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.

After fixing $$$c$$$, merge

with the reversed right part

to obtain one non-decreasing sequence. Process its $$$i$$$-th value $$$x$$$:

• 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$$$.
• Otherwise, we may assign any unused value smaller than $$$x$$$. Since $$$i-1$$$ values have already been used, there are $$$x-i+1$$$ choices.

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.

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)$$$.

#include <bits/stdc++.h>
using namespace std;

const int N = 1000000;
const int mod = 998244353;

int n;
int a[N + 10], vis[N + 10];
bool pre[N + 10], suf[N + 10];

void work() {
	cin >> n;
	for (int i = 1; i < n; ++i) cin >> a[i];
	a[n] = 0;

	for (int i = 1; i < n; ++i) {
		if (a[i] != n) continue;
		cout << 0 << '\n';
		return;
	}

	pre[0] = 1;
	for (int i = 1; i < n; ++i) pre[i] = pre[i - 1] && a[i] >= a[i - 1];
	suf[n] = 1;
	for (int i = n - 1; i >= 1; --i) suf[i] = suf[i + 1] && a[i] >= a[i + 1];

	long long ans = 0;
	for (int cut = 0; cut < n; ++cut) {
		if (!pre || !suf[cut + 1]) continue;
                if (cut > 0 && cut < n - 1 && a[cut] == a[cut + 1]) continue;

	        vector<int> l, r;
	        for (int i = 1; i <= cut; ++i) l.push_back(a[i]);
	        for (int i = cut + 1; i < n; ++i) r.push_back(a[i]);
	        reverse(r.begin(), r.end());

		memset(vis, 0, sizeof(int) * (n + 1));
		int x = 0, y = 0, used = 0;
		long long ways = 1;

		while (x < (int)l.size() || y < (int)r.size()) {
			int w;
			if (x == (int)l.size()) w = r[y++];
			else if (y == (int)r.size()) w = l[x++];
			else if (l[x] < r[y]) w = l[x++];
			else if (l[x] > r[y]) w = r[y++];
			else {
				cout << 0 << '\n';
				return;
			}

			if (!vis[w]) vis[w] = 1;
			else if (w < used) ways = 0;
			else ways = ways * (w - used) % mod;
			++used;
		}

		ans += ways;
	}

	cout << ans % mod << '\n';
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int T; cin >> T;
	while (T--) work();

	return 0;
}

Duplicate the permutation so that the cyclic sequence starting at any position becomes an ordinary contiguous segment of the duplicated array.

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.

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.

Checking every prefix separately for every starting position would introduce an additional factor of $$$n$$$. Instead, duplicate the permutation and define

For a starting position $$$l$$$, the successive cyclic prefixes become the ordinary segments $$$[l,l],[l,l+1],\ldots,[l,l+n-1]$$$.

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

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

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.

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$$$.

Therefore, inserting $$$x$$$ requires only three range additions:

1. Add $$$1$$$ to $$$[L,R]$$$.
2. If $$$x-1$$$ exists, subtract $$$1$$$ from $$$[L,\min(R,\operatorname{last}_{x-1})]$$$.
3. If $$$x+1$$$ exists, subtract $$$1$$$ from $$$[L,\min(R,\operatorname{last}_{x+1})]$$$.

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.

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)$$$.

#include <bits/stdc++.h>
using namespace std;

const int N = 200000;
const int inf = 1000000000;

int n;
int p[N + 10], last[N + 10];
int mx[4 * N + 10], lazy[4 * N + 10];

void apply(int u, int v) {
	mx[u] += v;
	lazy[u] += v;
}

void push(int u) {
	if (!lazy[u]) return;
	apply(u << 1, lazy[u]);
	apply(u << 1 | 1, lazy[u]);
	lazy[u] = 0;
}

void add(int u, int l, int r, int ql, int qr, int v) {
	if (ql <= l && r <= qr) {
		apply(u, v);
		return;
	}

	push(u);
	int mid = (l + r) >> 1;
	if (ql <= mid) add(u << 1, l, mid, ql, qr, v);
	if (qr > mid) add(u << 1 | 1, mid + 1, r, ql, qr, v);
	mx[u] = max(mx[u << 1], mx[u << 1 | 1]);
}

void add(int l, int r, int v) {
	if (l <= r) add(1, 1, n, l, r, v);
}

int find_bad(int u, int l, int r) {
	if (l == r) return l;

	push(u);
	int mid = (l + r) >> 1;
	if (mx[u << 1] > 2) return find_bad(u << 1, l, mid);
	return find_bad(u << 1 | 1, mid + 1, r);
}

void del(int u, int l, int r, int x) {
	if (l == r) {
		mx[u] = -inf;
		lazy[u] = 0;
		return;
	}

	push(u);
	int mid = (l + r) >> 1;
	if (x <= mid) del(u << 1, l, mid, x);
	else del(u << 1 | 1, mid + 1, r, x);
	mx[u] = max(mx[u << 1], mx[u << 1 | 1]);
}

void work() {
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> p[i];

	memset(last, 0, sizeof(int) * (n + 2));
	memset(mx, 0, sizeof(int) * (4 * n + 5));
	memset(lazy, 0, sizeof(int) * (4 * n + 5));

	int ans = n;
	for (int r = 1; r < 2 * n; ++r) {
		int L = max(1, r - n + 1), R = min(r, n);
		int x = p[(r - 1) % n + 1];

		add(L, R, 1);
		if (x > 1 && last[x - 1] >= L) add(L, min(R, last[x - 1]), -1);
		if (x < n && last[x + 1] >= L) add(L, min(R, last[x + 1]), -1);
		last[x] = r;

		while (mx[1] > 2) {
			int x = find_bad(1, 1, n);
			del(1, 1, n, x);
			--ans;
		}
	}

	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int T; cin >> T;
	while (T--) work();

	return 0;
}

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.

We need many values $$$h$$$ satisfying

How large is the XOR stabilizer of this set?

When $$$n$$$ is a power of two, pair the values as $$$y\leftrightarrow y\oplus x$$$, and place several complete pairs at odd positions.

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

The condition on every adjacent $$$2\times2$$$ submatrix implies

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$$$.

Let $$$L=\operatorname{lowbit}(n)$$$. The XOR stabilizer of $$$S$$$ is exactly

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$$$.

The necessary condition is therefore

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$$$.

We now describe the construction.

If $$$x=0$$$, set

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$$$.

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

Construct a permutation $$$p$$$ by placing the elements of $$$E$$$ at even positions and the elements of $$$O$$$ at odd positions. Then define

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.

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$$$.

The output contains $$$n^2$$$ numbers, so the time complexity is $$$O(n^2)$$$, and the extra space complexity is $$$O(n)$$$.

#include <bits/stdc++.h>
using namespace std;

const int N = 2500;

int n, x;
int vis[N + 10], in_o[N + 10], e[N + 10], o[N + 10], a[N + 10];
pair<int, int> p[N + 10];

bool check(int v) {
	return (v & (v - 1)) == 0;
}

void work() {
	cin >> n >> x;

	if (!check(n) || (x && n < 4)) {
		cout << -1 << '\n';
		return;
	}

	if (!x) {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				cout << (i ^ j) << (j + 1 == n ? '\n' : ' ');
			}
		}
		return;
	}

	for (int i = 0; i <= n; ++i) vis[i] = in_o[i] = e[i] = o[i] = a[i] = 0;

	int cnt = 0;
	for (int i = 0; i < n; ++i) {
		if (vis[i]) continue;
		int j = i ^ x;
		vis[i] = vis[j] = 1;
		p[++cnt] = {i, j};
	}

	for (int i = 1; i <= n / 4; ++i) in_o[p[i].first] = in_o[p[i].second] = 1;

	int ec = 0, oc = 0;
	for (int i = 0; i < n; ++i) {
		if (in_o[i]) o[++oc] = i;
		else e[++ec] = i;
	}

	ec = oc = 0;
	for (int i = 0; i < n; ++i) {
		if (i & 1) a[i] = o[++oc];
		else a[i] = e[++ec];
	}

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			int v = a[i] ^ a[j];
			if ((i & 1) && (j & 1)) v ^= x;
			cout << v << (j + 1 == n ? '\n' : ' ');
		}
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int T; cin >> T;
	while (T--) work();

	return 0;
}

Treat a prefix of length $$$k^i$$$ as one block. How can it be decomposed into smaller blocks?

Adding the same value to every character modulo $$$k$$$ produces only finitely many translated versions of the pattern-matching problem.

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.

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

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.

For the current pattern $$$t$$$, maintain the following information for every block:

• The number of occurrences of $$$t$$$ entirely inside the block.
• A prefix of the block of length at most $$$n-1$$$.
• A suffix of the block of length at most $$$n-1$$$.

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.

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.

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.

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

where $$$V=10^{17}$$$. The space complexity is $$$O(n+k^2\log_k V)$$$.

#include <bits/stdc++.h>
using namespace std;

struct node {
	long long v = 0;
	bool b = 0;
	string l = "", r = "";
	int l1, r1;
};

int n, k;
int fai[2000005];
long long T, ql, qr, trans[10][10];
long long ma, L, R;
node a[66][10], ans;
string pl[10], pr[10], s;

void make_fai() {
	for (int i = 1; i <= n; ++i) s[i] ^= 48;

	int l = 0;
	for (int i = 2; i <= n; ++i) {
		while (l && s[l + 1] != s[i]) l = fai[l];
		l += s[l + 1] == s[i];
		fai[i] = l;
	}
}

int val(string x) {
	int l = 0, res = 0;

	for (int i = 0; i < (int)x.size(); ++i) {
		while (l && s[l + 1] != x[i]) l = fai[l];
		l += s[l + 1] == x[i];
		if (l == n) ++res;
	}

	return res;
}

node add(node &x, node &y) {
	node res;

	if (x.b && y.b) {
		res.b = 1;
		res.l1 = x.l1;
		res.r1 = y.r1;
		res.v = x.v + y.v + trans[x.r1][y.l1];
		return res;
	}

	if (x.b) x.l = pl[x.l1], x.r = pr[x.r1];
	if (y.b) y.l = pl[y.l1], y.r = pr[y.r1];
	res.v = x.v + y.v + val(x.r + y.l);
	res.l = x.l;

	if ((int)res.l.size() < n - 1) {
		int t = min(n - 1 - (int)res.l.size(), (int)y.l.size());
		res.l += y.l.substr(0, t);
	}

	res.r = y.r;
	if ((int)res.r.size() < n - 1) {
		int t = min(n - 1 - (int)res.r.size(), (int)x.r.size());
		res.r = x.r.substr(x.r.size() - t, t) + res.r;
	}

	return res;
}

void init(long long x) {
	bool done = 0;

	for (long long cur = 1, i = 0; cur <= x; cur *= k, ++i) {
		ma = i;
		L = 0, R = cur;

		if (i == 0) {
			for (int j = 0; j < k; ++j) {
				if (n == 1) {
					a[0][j].v = j == s[1];
					a[0][j].b = 0;
					a[0][j].l = a[0][j].r = "";
				}
				else {
					a[0][j].v = 0;
					a[0][j].b = 0;
					a[0][j].l = a[0][j].r = "";
					a[0][j].l += (char)j;
					a[0][j].r = a[0][j].l;
				}
			}
		}
		else {
			for (int j = 0; j < k; ++j) {
				node cur;
				for (int t = 0; t < k; ++t) {
					if (!cur.v && !cur.b && cur.l.empty()) cur = a[i - 1][(j + t) % k];
					else cur = add(cur, a[i - 1][(j + t) % k]);
				}
				a[i][j] = cur;
			}
		}

		if (!done && cur >= n - 1) {
			done = 1;
			for (int j = 0; j < k; ++j) {
				pl[j] = a[i][j].l;
				pr[j] = a[i][j].r;
				a[i][j].b = 1;
				a[i][j].l1 = a[i][j].r1 = j;
				a[i][j].l = a[i][j].r = "";
			}
			for (int j = 0; j < k; ++j) {
				for (int t = 0; t < k; ++t) trans[j][t] = val(pr[j] + pl[t]);
			}
		}
	}
}

void calc(int dep, int st, long long l, long long r) {
	if (r <= ql || l > qr) return;

	if (ql <= l && r - 1 <= qr) {
		ans = add(ans, a[dep][st]);
		return;
	}

	node cur;
	long long len = r - l;

	for (int i = 0; i < k; ++i) {
		long long nl = l + len / k * i, nr = nl + len / k;

		if (ql <= nl && nr - 1 <= qr) {
			if (!cur.v && !cur.b && cur.l.empty()) cur = a[dep - 1][(st + i) % k];
			else cur = add(cur, a[dep - 1][(st + i) % k]);
			continue;
		}

		if (cur.v || cur.b || !cur.l.empty()) {
			ans = add(ans, cur);
			cur.v = 0, cur.b = 0;
			cur.l = cur.r = "";
		}
		calc(dep - 1, (st + i) % k, nl, nr);
	}

	if (cur.v || cur.b || !cur.l.empty()) ans = add(ans, cur);
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> k >> T;
	while (T--) {
		cin >> ql >> qr >> n >> s;
		s = " " + s + "!";

		make_fai();
		init(qr);
		++ma, R *= k;

		ans.v = 0, ans.b = 0;
		ans.l = ans.r = "";
		calc(ma, 0, L, R);
		cout << ans.v << '\n';
	}

	return 0;
}

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.

Let

Inside a complete block, $$$d_i$$$ is always $$$1$$$. Therefore, all positions with $$$d_i\ne1$$$ must have the same residue modulo $$$k$$$.

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$$$.

First examine the block structure of the infinite string $$$s$$$. Every block of length $$$k$$$ is a cyclic shift of

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$$$.

To determine the alignment, consider the adjacent differences of $$$t$$$ modulo $$$k$$$:

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.

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.

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$$$.

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.

We are left with occurrence queries for patterns of length $$$1$$$ or $$$2$$$.

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.

For a pattern of length $$$2$$$, precompute

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.

The total time complexity is

where $$$V=10^{17}$$$.

#include<bits/stdc++.h>
#define int long long
using namespace std;
int lg;
int q,L,R,n,k,d[10000005],t[100],b[100];
char c[10000005],s[10000005];
struct node{
	int f[65][65];
}sum[65][65];
node merge(node a,node b,int v=1){
	for(int i=0;i<k;i++){
		for(int j=0;j<k;j++){
			a.f[(i+v)%k][(j+v)%k]+=b.f[i][j];
		}
	}
	return a;
}
int calc(int x){
	int sum=0;
	while(x){
		sum+=x%k;
		x=x/k;
	}
	return sum%k;
}
int sp[70];
int gs(int r,int x,int y){
    // Count occurrences of the pattern "xy" in the range [0, r].
	r++;
	int cnt=0,xnow=0,ans=0,lowbit=0;
	for(int i=0;i<=lg;i++){
		sp[i]=r%k;r/=k;
	}
	for(int i=lg;i>=0;i--){
		int j=sp[i];
		if(!j) continue;
		ans+=sum[i][j].f[(x+(k-1)*cnt)%k][(y+(k-1)*cnt)%k];
		if(xnow){
			int px=(cnt-1+lowbit*(k-1))%k,py=cnt%k;
			if(px==x&&py==y){
				ans++;
			}
		}
		xnow+=b[i]*j;
		cnt+=j;
		lowbit=i;
	}
	return ans;
}
int gs(int r,int x){
    // Count occurrences of the pattern "x" in the range [0, r].
	r++;
	int sum=r/k,pl=r/k*k,y=calc(pl);
	while(pl<r){
		if(y==x){
			sum++;
			break;
		}
		pl++;
		y++;
		y>=k?y-=k:0;
	}
	return sum;
}
void print(char c){
	if(c<10){
		cout<<char(c+'0');
	}else{
		cout<<char(c+'a'-10);
	}
}
int ans=0;
void solve(int l,int r,int n){
    // Compute the answer recursively.
	if(l>r){
		return ;
	}
	for(int i=0;i<k;i++){
		t[i]=0;
	}
	if(n<=2){
        // For length at most 2, use prefix-count differences directly.
		if(n==2){
			int pl=c[0],pr=c[1];
			int sum=gs(r,pl,pr)-gs(l,pl,pr);
			ans+=sum;
			return ;
		}else{
			int sum=0;
			sum=gs(r,c[0])-gs(l-1,c[0]);
			ans+=sum;
			return ;
		}
	}
	int cnt=0;
	for(int i=1;i<n;i++){
		d[i]=(c[i]-c[i-1]+k)%k;
		if(d[i]!=1){
			if(!t[i%k]) cnt++;
			t[i%k]=1;
		}
	}
	if(cnt>1){
        // If more than one residue occurs, the pattern cannot appear.
		return ;
	}
	int m=0,pl=k,pr=k,p=0;
	if(cnt){
        // At least one adjacent difference is not 1.
		for(int i=1;i<n;i++){
			if(d[i]!=1) p=i%k;
		}
		if(p){
			pl=p;
			s[m++]=(c[p-1]+1)%k;
		}
		for(int i=p;i<n;i+=k){
			if(i+k-1>=n) pr=n-i;
			s[m++]=c[i];
		}

        // Handle the two partial boundary blocks separately.
		int bl=(r/k)*k,br=(l/k+1)*k-1;
		if(br-l+1<pl) l=l/k+1;
		else l=l/k;
		if(r-bl+1<pr) r=r/k-1;
		else r=r/k;

		for(int i=0;i<m;i++) c[i]=s[i];
		solve(l,r,m);
	}else{
        // Every adjacent difference is 1.
		int szl=(l/k+1)*k-l,szr=r-(r/k)*k+1,L,R;
		if(n<=k){
			int x=c[0];
			for(int i=0;i+n-1<k;i++){
				c[0]=(x-i+k)%k;
                // Handle the two partial boundary blocks separately.
				pl=k-i,pr=i+n;
				if(szl<pl) L=l/k+1;
				else L=l/k;
				if(szr<pr) R=r/k-1;
				else R=r/k;
				solve(L,R,1);
			}
		}
		for(int i=0;i<n;i++){
			s[i]=c[i];
		}
		for(int i=0;i<min(n-1,k);i++){
            // Handle the two partial boundary blocks separately.
			pl=i+1,pr=n-1-i;
			if(pr>k) continue;
			if(szl<pl) L=l/k+1;
			else L=l/k;
			if(szr<pr) R=r/k-1;
			else R=r/k;
			c[0]=c[1]=s[i+1];
			solve(L,R,2);
		}
	}
}
char change(int x){
    if(0<=x&&x<=9) return x+'0';
    if(10<=x&&x<=35) return x-10+'A';
    if(36<=x&&x<=61) return x-36+'a';
}
int change(char x){
    if('0'<=x&&x<='9') return x-'0';
    if('A'<=x&&x<='Z') return x+10-'A';
    if('a'<=x&&x<='z') return x+36-'a';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>k>>q;

    // sum[i][j] stores counts of length-2 substrings in the first j * k^i characters.
	b[0]=1;lg=0;
	for(int i=1;i<=k;i++){
		for(int j=1;j<i;j++){
			sum[0][i].f[j-1][j]=1;
		}
	}
	for(int p=1;p;p++){
		b[p]=b[p-1]*k;
		lg++;
		if(b[p]>1e17){
			break;
		}
		sum[p][1]=sum[p-1][k];
        // Concatenate the k shifted blocks.
		for(int i=2;i<=k;i++){
			sum[p][i]=merge(sum[p][i-1],sum[p-1][k],i-1);
			// Count substrings that cross a block boundary directly.
			sum[p][i].f[calc(b[p]*(i-1)-1)][calc(b[p]*(i-1))]++;
		}
	}

	while(q--){
		cin>>L>>R>>n;
		cin>>c;
		for(int i=0;i<n;i++){
			c[i]=change(c[i]);
		}
		solve(L,R,n);
		cout<<ans<<endl;
		ans=0;
	}
    return 0;
}

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?

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.

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.

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.

First, consider the degree pattern of a simple path from vertex $$$1$$$ to vertex $$$n$$$:

• vertices $$$1$$$ and $$$n$$$ have degree $$$1$$$ in the path;
• every other used vertex has degree $$$2$$$;
• every unused vertex has degree $$$0$$$.

We will build an auxiliary graph where:

• an unused vertex corresponds to one internal matching edge;
• a used internal vertex must match both of its copies to other vertices;
• vertices $$$1$$$ and $$$n$$$ have only one copy each, so they contribute exactly one path edge.

Then a perfect matching in the auxiliary graph will describe a path in the original graph.

Let the original graph be $$$G=(V,E)$$$.

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

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$$$.

Also, the deleted copies are in different layers. This is what forces the restored path to have even length.

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$$$.

For every internal vertex $$$v\notin{1,n}$$$, add the cross-layer edge $$$(L(v),R(v))$$$ with weight $$$M$$$.

Here $$$M$$$ is a sufficiently large constant, for example any $$$M \gt |V'|$$$.

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.

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.

Meaning of a Perfect Matching

Consider a perfect matching $$$S$$$ of $$$G'$$$.

For an internal vertex $$$v\notin{1,n}$$$, both $$$L(v)$$$ and $$$R(v)$$$ must be matched.

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.

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$$$.

Vertices $$$1$$$ and $$$n$$$ have only one copy each and have no cross-layer edge, so they naturally have degree $$$1$$$.

Thus the selected same-layer edges map to a subgraph of the original graph in which:

• vertices $$$1$$$ and $$$n$$$ have degree $$$1$$$;
• every other vertex has degree $$$0$$$ or $$$2$$$.

So this subgraph consists of one path from $$$1$$$ to $$$n$$$ and possibly several cycles.

We now prove the construction in both directions and then explain why maximum weight removes the cycles and minimizes the path length.

Proof 1: Every Even Simple Path Gives a Perfect Matching

Suppose we have an even-length simple path

where $$$2\mid L$$$.

Choose edges along this path alternately:

• for the first edge $$$(p_0,p_1)$$$, choose $$$(L(p_0),L(p_1))$$$;
• for the second edge $$$(p_1,p_2)$$$, choose $$$(R(p_1),R(p_2))$$$;
• for the third edge, choose the corresponding left-layer edge;
• for the fourth edge, choose the corresponding right-layer edge;
• and so on.

Since $$$L$$$ is even, the last path edge $$$(p_{L-1},p_L)$$$ is chosen in the right layer, and $$$R(n)$$$ exists.

For every internal vertex $$$v$$$ not on the path, choose the cross-layer edge $$$(L(v),R(v))$$$.

Now every vertex of $$$G'$$$ is matched exactly once, so we have constructed a perfect matching.

Proof 2: Every Perfect Matching Gives an Even Simple Path

Take any perfect matching of $$$G'$$$ and map all selected same-layer edges back to the original graph.

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.

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))$$$.

Therefore the original edges on the path must appear as

So the number of original edges on this path is even.

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.

Proof 3: A Maximum-Weight Perfect Matching Has No Extra Cycles

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.

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

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.

This is still a valid perfect matching. The affected part now has total weight

Since $$$kM \gt k(M-1)$$$, the matching weight increases, which contradicts maximality.

Therefore a maximum-weight perfect matching cannot produce extra cycles. It restores exactly one even-length simple path from $$$1$$$ to $$$n$$$.

Proof 4: The Restored Path Is Shortest

In any perfect matching of $$$G'$$$, the number of matched edges is fixed.

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.

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.

Finding the Matching and Restoring the Path

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.

The auxiliary graph has $$$2n-2$$$ vertices and at most $$$2m+n-2$$$ edges. The weighted blossom algorithm runs in $$$O(|V'|^3)$$$ time.

After computing the maximum-weight matching:

• if its size is not $$$|V'|/2$$$, output $$$-1$$$;
• otherwise, take the symmetric difference between the matching edges and all cross-layer edges $$$(L(v),R(v))$$$ for $$$v\notin{1,n}$$$.

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.

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$$$.

#include <bits/stdc++.h>
using namespace std;

const int N = 1000;
const int V = 2 * N;
const int B = 2 * V;
const int inf = 0x3f3f3f3f;
const int big = 10000;

struct edge {
	int u, v, w;
};

int n, m;
int idL[N + 10], idR[N + 10], ori[V + 10];
int init_u[N + 10], init_v[N + 10], init_cnt;
char sx[V + 10][V + 10];
vector<int> adj[V + 10];

struct blossom_tree {
	int n, nx;
	edge g[B + 10][B + 10];
	int lab[B + 10], match[B + 10], slack[B + 10], st[B + 10], pa[B + 10];
	int flower_from[B + 10][V + 10], flower[B + 10][V + 10];
	int S[B + 10], vis[B + 10], flower_cnt[B + 10], tmp[V + 10];
	queue<int> q;

	void init(int _n) {
		n = _n, nx = n;

		for (int i = 0; i <= 2 * n + 2; ++i) {
			lab[i] = match[i] = slack[i] = st[i] = pa[i] = S[i] = vis[i] = 0;
			flower_cnt[i] = 0;
			for (int j = 0; j <= n; ++j) flower_from[i][j] = 0;
		}

		for (int i = 1; i <= 2 * n + 2; ++i) {
			for (int j = 1; j <= 2 * n + 2; ++j) g[i][j] = {i, j, 0};
		}
	}

	void add_edge(int u, int v, int w) {
		if (u == v) return;

		if (w > g[u][v].w) {
			g[u][v] = {u, v, w};
			g[v][u] = {v, u, w};
		}
	}

	int e_delta(edge e) {
		return lab[e.u] + lab[e.v] - g[e.u][e.v].w * 2;
	}

	void update_slack(int u, int x) {
		if (!slack[x] || e_delta(g[u][x]) < e_delta(g[slack[x]][x])) slack[x] = u;
	}

	void set_slack(int x) {
		slack[x] = 0;

		for (int u = 1; u <= n; ++u) {
			if (g[u][x].w && st[u] != x && S[st[u]] == 0) update_slack(u, x);
		}
	}

	void q_push(int x) {
		if (x <= n) q.push(x);
		else {
			for (int i = 0; i < flower_cnt[x]; ++i) q_push(flower[x][i]);
		}
	}

	void set_st(int x, int b) {
		st[x] = b;

		if (x > n) {
			for (int i = 0; i < flower_cnt[x]; ++i) set_st(flower[x][i], b);
		}
	}

	void reverse_flower(int b, int l, int r) {
		while (l < r) {
			swap(flower[b][l], flower[b][r]);
			++l, --r;
		}
	}

	void rotate_flower(int b, int pr) {
		int cnt = flower_cnt[b];

		for (int i = 0; i < cnt; ++i) tmp[i] = flower[b][(i + pr) % cnt];
		for (int i = 0; i < cnt; ++i) flower[b][i] = tmp[i];
	}

	int get_pr(int b, int xr) {
		int pr = 0;

		while (flower[b][pr] != xr) ++pr;

		if (pr & 1) {
			reverse_flower(b, 1, flower_cnt[b] - 1);
			return flower_cnt[b] - pr;
		}

		return pr;
	}

	void set_match(int u, int v) {
		match[u] = g[u][v].v;

		if (u > n) {
			edge e = g[u][v];
			int xr = flower_from[u][e.u];
			int pr = get_pr(u, xr);

			for (int i = 0; i < pr; ++i) set_match(flower[u][i], flower[u][i ^ 1]);

			set_match(xr, v);
			rotate_flower(u, pr);
		}
	}

	void augment(int u, int v) {
		while (true) {
			int xnv = st[match[u]];

			set_match(u, v);

			if (!xnv) return;

			set_match(xnv, st[pa[xnv]]);
			u = st[pa[xnv]], v = xnv;
		}
	}

	int get_lca(int u, int v) {
		static int tim = 0;
		++tim;

		while (u || v) {
			if (u) {
				if (vis[u] == tim) return u;

				vis[u] = tim;
				u = st[match[u]];

				if (u) u = st[pa[u]];
			}

			swap(u, v);
		}

		return 0;
	}

	void add_blossom(int u, int lca, int v) {
		int b = n + 1;

		while (b <= nx && st[b]) ++b;
		if (b > nx) ++nx;

		lab[b] = 0, S[b] = 0, match[b] = match[lca];
		flower_cnt[b] = 0;
		flower[b][flower_cnt[b]++] = lca;

		for (int x = u, y; x != lca; x = st[pa[y]]) {
			flower[b][flower_cnt[b]++] = x;
			y = st[match[x]];
			flower[b][flower_cnt[b]++] = y;
			q_push(y);
		}

		reverse_flower(b, 1, flower_cnt[b] - 1);

		for (int x = v, y; x != lca; x = st[pa[y]]) {
			flower[b][flower_cnt[b]++] = x;
			y = st[match[x]];
			flower[b][flower_cnt[b]++] = y;
			q_push(y);
		}

		set_st(b, b);

		for (int x = 1; x <= nx; ++x) {
			g[b][x] = {b, x, 0};
			g[x][b] = {x, b, 0};
		}

		for (int x = 1; x <= n; ++x) flower_from[b][x] = 0;

		for (int i = 0; i < flower_cnt[b]; ++i) {
			int xs = flower[b][i];

			for (int x = 1; x <= nx; ++x) {
				if (g[xs][x].w && (!g[b][x].w || e_delta(g[xs][x]) < e_delta(g[b][x]))) {
					g[b][x] = g[xs][x];
					g[x][b] = g[x][xs];
				}
			}

			for (int x = 1; x <= n; ++x) {
				if (flower_from[xs][x]) flower_from[b][x] = xs;
			}
		}

		set_slack(b);
	}

	void expand_blossom(int b) {
		for (int i = 0; i < flower_cnt[b]; ++i) set_st(flower[b][i], flower[b][i]);

		int xr = flower_from[b][g[b][pa[b]].u];
		int pr = get_pr(b, xr);

		for (int i = 0; i < pr; i += 2) {
			int xs = flower[b][i];
			int xns = flower[b][i + 1];

			pa[xs] = g[xns][xs].u;
			S[xs] = 1, S[xns] = 0;
			slack[xs] = 0;

			set_slack(xns);
			q_push(xns);
		}

		S[xr] = 1;
		pa[xr] = pa[b];

		for (int i = pr + 1; i < flower_cnt[b]; ++i) {
			int xs = flower[b][i];

			S[xs] = -1;
			set_slack(xs);
		}

		st[b] = 0;
	}

	bool on_found_edge(edge e) {
		int u = st[e.u], v = st[e.v];

		if (S[v] == -1) {
			pa[v] = e.u;
			S[v] = 1;

			int nu = st[match[v]];

			slack[v] = slack[nu] = 0;
			S[nu] = 0;

			q_push(nu);
		}
		else if (S[v] == 0) {
			int lca = get_lca(u, v);

			if (!lca) {
				augment(u, v);
				augment(v, u);
				return true;
			}
			else add_blossom(u, lca, v);
		}

		return false;
	}

	bool matching() {
		for (int i = 1; i <= nx; ++i) S[i] = -1, slack[i] = 0;

		while (!q.empty()) q.pop();

		for (int x = 1; x <= nx; ++x) {
			if (st[x] == x && !match[x]) {
				pa[x] = 0;
				S[x] = 0;
				q_push(x);
			}
		}

		if (q.empty()) return false;

		while (true) {
			while (!q.empty()) {
				int u = q.front(); q.pop();
				if (S[st[u]] == 1) continue;

				for (int v = 1; v <= n; ++v) {
					if (g[u][v].w && st[u] != st[v]) {
						if (!e_delta(g[u][v])) {
							if (on_found_edge(g[u][v])) return true;
						}
						else update_slack(u, st[v]);
					}
				}
			}

			int d = inf;

			for (int u = 1; u <= n; ++u) {
				if (S[st[u]] == 0) d = min(d, lab[u]);
			}

			for (int b = n + 1; b <= nx; ++b) {
				if (st[b] == b && S[b] == 1) d = min(d, lab[b] / 2);
			}

			for (int x = 1; x <= nx; ++x) {
				if (st[x] == x && slack[x]) {
					if (S[x] == -1) d = min(d, e_delta(g[slack[x]][x]));
					else if (S[x] == 0) d = min(d, e_delta(g[slack[x]][x]) / 2);
				}
			}

			if (d == inf) return false;

			for (int u = 1; u <= n; ++u) {
				if (S[st[u]] == 0) {
					if (lab[u] == d) return false;
					lab[u] -= d;
				}
				else if (S[st[u]] == 1) lab[u] += d;
			}

			for (int b = n + 1; b <= nx; ++b) {
				if (st[b] == b) {
					if (S[b] == 0) lab[b] += d * 2;
					else if (S[b] == 1) lab[b] -= d * 2;
				}
			}

			while (!q.empty()) q.pop();

			for (int x = 1; x <= nx; ++x) {
				if (st[x] == x && slack[x] && st[slack[x]] != x && !e_delta(g[slack[x]][x])) {
					if (on_found_edge(g[slack[x]][x])) return true;
				}
			}

			for (int b = n + 1; b <= nx; ++b) {
				if (st[b] == b && S[b] == 1 && !lab[b]) expand_blossom(b);
			}
		}
	}

	int solve() {
		nx = n;
		int cnt = 0, mx = 0;

		for (int i = 0; i <= 2 * n + 2; ++i) {
			lab[i] = match[i] = slack[i] = pa[i] = S[i] = vis[i] = 0;
			st[i] = 0;
			flower_cnt[i] = 0;
		}

		for (int i = 0; i <= n; ++i) st[i] = i;

		for (int u = 1; u <= n; ++u) {
			for (int v = 1; v <= n; ++v) {
				flower_from[u][v] = (u == v ? u : 0);
				mx = max(mx, g[u][v].w);
			}
		}

		for (int u = 1; u <= n; ++u) lab[u] = mx;

		while (matching()) ++cnt;
		return cnt;
	}
} blossom;

int new_node(int x, int &tot) {
	ori[tot + 1] = x;
	return ++tot;
}

void toggle_edge(int u, int v) {
	if (u > v) swap(u, v);
	sx[u][v] ^= 1;
}

void work() {
	cin >> n >> m;

	memset(idL, -1, sizeof(idL));
	memset(idR, -1, sizeof(idR));

	int tot = 0;

	for (int i = 1; i <= n; ++i) {
		if (i != n) idL[i] = new_node(i, tot);
	}
	for (int i = 1; i <= n; ++i) {
		if (i != 1) idR[i] = new_node(i, tot);
	}

	blossom.init(tot);

	for (int i = 1; i <= m; ++i) {
		int u, v; cin >> u >> v;

		if (idL[u] != -1 && idL[v] != -1) blossom.add_edge(idL[u], idL[v], big - 1);
		if (idR[u] != -1 && idR[v] != -1) blossom.add_edge(idR[u], idR[v], big - 1);
	}

	init_cnt = 0;

	for (int i = 2; i < n; ++i) {
		blossom.add_edge(idL[i], idR[i], big);
		init_u[++init_cnt] = idL[i], init_v[init_cnt] = idR[i];
	}

	int cnt = blossom.solve();

	if (cnt != tot / 2) {
		cout << -1 << '\n';
		return;
	}

	for (int i = 1; i <= tot; ++i) {
		adj[i].clear();
		for (int j = 1; j <= tot; ++j) sx[i][j] = 0;
	}

	for (int i = 1; i <= tot; ++i) {
		if (blossom.match[i] && i < blossom.match[i]) toggle_edge(i, blossom.match[i]);
	}

	for (int i = 1; i <= init_cnt; ++i) toggle_edge(init_u[i], init_v[i]);

	for (int i = 1; i <= tot; ++i) {
		for (int j = i + 1; j <= tot; ++j) {
			if (sx[i][j]) {
				adj[i].push_back(j);
				adj[j].push_back(i);
			}
		}
	}

	int st = idL[1], ed = idR[n];
	vector<int> aux, path;
	int last = 0, cur = st;

	while (true) {
		aux.push_back(cur);
		if (cur == ed) break;

		int nxt = 0;

		for (int v : adj[cur]) {
			if (v != last) {
				nxt = v;
				break;
			}
		}

		if (!nxt) {
			cout << -1 << '\n';
			return;
		}

		last = cur, cur = nxt;

		if ((int)aux.size() > tot + 5) {
			cout << -1 << '\n';
			return;
		}
	}

	path.push_back(1);
	for (int i = 1; i < (int)aux.size(); ++i) {
		int u = aux[i - 1], v = aux[i];
		if (ori[u] != ori[v]) path.push_back(ori[v]);
	}

	if (path.back() != n || ((int)path.size() - 1) % 2) {
		cout << -1 << '\n';
		return;
	}

	cout << (int)path.size() - 1 << '\n';
	for (int i = 0; i < (int)path.size(); ++i) {
		if (i) cout << ' ';
		cout << path[i];
	}
	cout << '\n';
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int T; cin >> T;
	while (T--) work();

	return 0;
}