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;
	}
	if (n == 5 && k == 2) {
		cout << "01110\n";
		return;
	}
	if (n == 6 && k == 1) {
		cout << "101001\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;

		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]);

		if (!l.empty() && !r.empty() && l.back() == r.front()) continue;
		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 >> T >> k;
	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.

Auxiliary-Graph Construction

The main difficulty is the simple-path constraint. We encode the degree structure of a simple path as a matching.

A simple path from vertex $$$1$$$ to vertex $$$n$$$ satisfies the following degree conditions:

• Vertices $$$1$$$ and $$$n$$$ have degree $$$1$$$ in the path.
• Every other used vertex has degree $$$2$$$.
• Every unused vertex has degree $$$0$$$.

For every vertex $$$v$$$ of the original graph $$$G=(V,E)$$$, create two copies, $$$L(v)$$$ and $$$R(v)$$$, and then remove $$$R(1)$$$ and $$$L(n)$$$. The vertex set of the auxiliary graph $$$G'=(V',E')$$$ is

Removing these two copies ensures that vertices $$$1$$$ and $$$n$$$ contribute exactly one path edge each. Because the removed copies belong to different layers, the recovered path is also forced 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 endpoint copies exist. Give each of these edges weight $$$M-1$$$.

For every internal vertex $$$v\notin{1,n}$$$, add a cross-layer edge $$$(L(v),R(v))$$$ of weight $$$M$$$, where $$$M$$$ is any constant greater than $$$|V'|$$$.

Compute a maximum-weight matching in the general graph $$$G'$$$. If it is not perfect, no valid path exists. Otherwise, the answer can be recovered from it. Since $$$M \gt |V'|$$$, whenever a perfect matching exists, losing one matching edge decreases the weight by more than all possible gains obtained by replacing the remaining edges. Therefore, a maximum-weight matching must be perfect.

Interpretation of a Perfect Matching

Consider a perfect matching $$$S$$$.

For an internal vertex $$$v$$$, if $$$S$$$ contains the cross-layer edge $$$(L(v),R(v))$$$, then $$$v$$$ is unused, corresponding to degree $$$0$$$ in the original graph.

Otherwise, $$$L(v)$$$ and $$$R(v)$$$ are each matched by a same-layer edge, so $$$v$$$ has degree $$$2$$$ in the original graph.

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

Thus, mapping all selected same-layer edges back to the original graph yields a path from $$$1$$$ to $$$n$$$, together with zero or more vertex-disjoint cycles.

Why the Path Length Is Even

Suppose there is an even-length simple path

Choose same-layer edges alternately along the path: use the left layer for the first edge, the right layer for the second edge, and so on. Since $$$L$$$ is even, the last edge lies in the right layer and reaches the existing copy $$$R(n)$$$. Every internal vertex not on the path is matched by its own cross-layer edge, producing a perfect matching.

Conversely, take the symmetric difference of any perfect matching with the set of all cross-layer edges. The component containing $$$L(1)$$$ alternates between same-layer matching edges and cross-layer edges and eventually reaches $$$R(n)$$$. Consequently, it contains an even number of original edges. It has exactly two vertices of degree $$$1$$$, while every other vertex has degree $$$2$$$, so it corresponds to an even-length simple path.

Why Maximum Weight Eliminates Cycles

Suppose the recovered structure contains a cycle with $$$c$$$ vertices. The cycle uses $$$c$$$ same-layer matching edges of weight $$$M-1$$$, for a total weight of $$$c(M-1)$$$.

Remove these edges and instead select the cross-layer edge of every vertex on the cycle. This still gives a perfect matching, but the total weight contributed by these vertices becomes $$$cM$$$, which is strictly larger. This contradicts maximality. Therefore, a maximum-weight perfect matching contains no extra cycle.

Why the Recovered Path Is Shortest

Every perfect matching contains the same number of edges. Cross-layer edges have weight $$$M$$$, while same-layer edges have weight $$$M-1$$$, so maximizing the total weight is equivalent to minimizing the number of same-layer edges.

A maximum-weight matching contains no extra cycles, so its same-layer edges correspond exactly to the edges of the recovered path. Hence, the recovered path is the shortest even-length simple path.

Matching and Path Recovery

The auxiliary graph has $$$2n-2$$$ vertices and at most $$$2m+n-2$$$ edges. We therefore use a maximum-weight matching algorithm for general graphs, such as the weighted blossom algorithm, whose time complexity is $$$O(|V'|^3)$$$.

After finding the matching:

1. If its size is not $$$|V'|/2$$$, output $$$-1$$$.
2. Take the symmetric difference between the matching and the set of cross-layer edges of all internal vertices.
3. The cross-layer edges of unused vertices cancel, and the remaining auxiliary graph is exactly a path from $$$L(1)$$$ to $$$R(n)$$$.
4. Traverse this path and record the corresponding original vertex whenever a same-layer edge is crossed.

This recovers the required shortest even-length simple path.

#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;
}