每一个 bool 变量表示「\(a_i\) 是否 \(\ge j\)」，由于 \(a_i\) 必然 \(\ge1\)，所以总的变量数是 \(n(k-1)\)。
然后我们根据题目条件来建有向边，注意 2-sat 要满足对称性，所以下文中每一个条件的逆否命题都要建边：
- \(a_i\le a_{i+1}\)，等价于「对于所有的 \(v\)，若 \(a_i\ge v\)，则 \(a_{i+1}\ge v\)」。
- \(a_i\ne x\)，等价于「若 \(a_i\ge x\)，则 \(a_i\ge x+1\)」。
- \(a_i+a_j\le x\)，等价于「对于所有的 \(v\)，若 \(a_i\ge v\)，则 \(¬(a_j\ge x-v+1)\)」。
- \(a_i+a_j\ge x\)，等价于「对于所有的 \(v\)，若 \(¬(a_i\ge v)\)，则 \(a_j\ge x-v+1\)」。
当然，还有最浅显的：
- 若 \(a_i\ge v\)，则 \(a_i\ge v-1\)。
麻烦的建图处理完后就是板子了。
Code：
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 360005;
int T;
int n, m, k;
int dfn[N], low[N], tim;
int stk[N], top; bool vis[N];
int bel[N], scc_cnt;
vector <int> G[N];
void addedge(int x, int y) { G[x].pb(y); if (x != (y ^ 1)) G[y ^ 1].pb(x ^ 1); }
int num(int id, int x, bool y) { return ((id - 1) * (k - 1) + (x - 2)) << 1 | y; }
void build(int x) { for (int i = 2; i < k; ++i) addedge(num(x, i, 0), num(x, i + 1, 0)); }
void le(int x, int y) { for (int i = 2; i <= k; ++i) addedge(num(x, i, 1), num(y, i, 1)); }
void ne(int x, int val) {
if (val == 1) addedge(num(x, 2, 0), num(x, 2, 1));
else if (val == k) addedge(num(x, k, 1), num(x, k, 0));
else addedge(num(x, val, 1), num(x, val + 1, 1));
}
void sumle(int x, int y, int val) {
for (int i = 2; i <= k; ++i) {
if (i >= val) addedge(num(x, i, 1), num(x, i, 0)), addedge(num(y, i, 1), num(y, i, 0));
else if (i + k > val) addedge(num(x, i, 1), num(y, val - i + 1, 0));
}
}
void sumge(int x, int y, int val) {
for (int i = 2; i <= k; ++i) {
if (i + k <= val) addedge(num(x, i, 0), num(x, i, 1)), addedge(num(y, i, 0), num(y, i, 1));
else if (i < val) addedge(num(x, i, 0), num(y, val - i + 1, 1));
}
}
void Tarjan(int u) {
dfn[u] = low[u] = ++tim, vis[stk[++top] = u] = 1;
for (int v : G[u]) {
if (!dfn[v]) Tarjan(v), low[u] = min(low[u], low[v]);
else if (vis[v]) low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u]) {
++scc_cnt;
do {
bel[stk[top]] = scc_cnt;
vis[stk[top]] = 0;
--top;
} while (stk[top + 1] ^ u);
}
}
void solve() {
scanf("%d%d%d", &n, &m, &k);
int tot = (k - 1) * n * 2;
for (int i = 0; i < tot; ++i) G[i].clear();
for (int i = 1; i <= n; ++i) build(i);
for (int i = 1; i < n; ++i) le(i, i + 1);
for (int i = 1, ty, x, y, val; i <= m; ++i) {
scanf("%d", &ty);
if (ty == 1) scanf("%d%d", &x, &val), ne(x, val);
if (ty == 2) scanf("%d%d%d", &x, &y, &val), sumle(x, y, val);
if (ty == 3) scanf("%d%d%d", &x, &y, &val), sumge(x, y, val);
}
memset(dfn, 0, sizeof (int) * tot), memset(bel, 0, sizeof (int) * tot), tim = top = scc_cnt = 0;
for (int i = 0; i < tot; ++i) if (!dfn[i]) Tarjan(i);
for (int i = 0; i < tot; i += 2) if (bel[i] == bel[i ^ 1]) return printf("%d\n", -1), void();
for (int i = 1; i <= n; ++i) {
int val = 1;
for (int j = 2; j <= k; ++j) if (bel[num(i, j, 1)] < bel[num(i, j, 0)]) val = j;
printf("%d ", val);
}
printf("\n");
}
int main() {
scanf("%d", &T);
while (T--) solve();
return 0;
}