Too Many Constraints
Contest: Educational Codeforces Round 130 (Rated for Div. 2)
Difficulty rating: 2800
Tags: 2-sat, constructive algorithms, graphs, implementation

You are asked to build an array $$$a$$$, consisting of $$$n$$$ integers, each element should be from $$$1$$$ to $$$k$$$.

The array should be non-decreasing ($$$a_i \le a_{i+1}$$$ for all $$$i$$$ from $$$1$$$ to $$$n-1$$$).

You are also given additional constraints on it. Each constraint is of one of three following types:

- $$$1~i~x$$$: $$$a_i$$$ should not be equal to $$$x$$$;
- $$$2~i~j~x$$$: $$$a_i + a_j$$$ should be less than or equal to $$$x$$$;
- $$$3~i~j~x$$$: $$$a_i + a_j$$$ should be greater than or equal to $$$x$$$.

Build any non-decreasing array that satisfies all constraints or report that no such array exists.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of each testcase contains three integers $$$n, m$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^4$$$; $$$0 \le m \le 2 \cdot 10^4$$$; $$$2 \le k \le 10$$$).

The $$$i$$$-th of the next $$$m$$$ lines contains a description of a constraint. Each constraint is of one of three following types:

- $$$1~i~x$$$ ($$$1 \le i \le n$$$; $$$1 \le x \le k$$$): $$$a_i$$$ should not be equal to $$$x$$$;
- $$$2~i~j~x$$$ ($$$1 \le i < j \le n$$$; $$$2 \le x \le 2 \cdot k$$$): $$$a_i + a_j$$$ should be less than or equal to $$$x$$$;
- $$$3~i~j~x$$$ ($$$1 \le i < j \le n$$$; $$$2 \le x \le 2 \cdot k$$$): $$$a_i + a_j$$$ should be greater than or equal to $$$x$$$.

The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^4$$$. The sum of $$$m$$$ over all testcases doesn't exceed $$$2 \cdot 10^4$$$.

Output format:
For each testcase, determine if there exists a non-decreasing array that satisfies all conditions. If there is no such array, then print -1. Otherwise, print any valid array — $$$n$$$ integers from $$$1$$$ to $$$k$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
4
4 0 4
2 2 3
3 1 2 3
1 2 2
3 3 2
1 1 1
2 2 3 2
3 2 3 2
5 5 5
3 2 5 7
2 4 5 10
3 4 5 6
3 3 4 7
2 1 5 7

Example output:
1 2 3 4
1 3
-1
1 2 2 5 5

Editorial:
Imagine there were no constraints of the second or the third types. Then it would be possible to solve the problem with some greedy algorithm. Unfortunately, when both these constraints are present, it's not immediately clear how to adapt the greedy.
Dynamic programming is probably also out of question, because you can't maintain all possible cuts between equal values on each prefix.
Thus, let's try to make a graph problem out of this. Who knows, maybe a flow or something else could work.
Create $$$k$$$ nodes for each position. Let the $$$x$$$-th of them on the $$$i$$$-th position represent the condition of kind "is $$$a_i$$$ equal to $$$x$$$?". Then all constraints can be described as edges on this graph. Binary variables, restrictive edges. Surely, this is 2-SAT.
Connect the pairs of values that satisfy each constraint. Add the edges between the adjacent positions to enforce the restriction on the non-decreasing order. Prohibit each position to be assigned to multiple values. Force each position to be assigned at least one value. Huh, it's not that easy. That's where the 2-SAT idea fails. We want the conditions of form $$$(a_i = 1 \vee a_i = 2 \vee \dots \vee a_i = k)$$$. But that is not allowed, since 2-SAT has to have two variables in a clause.
That's where the main idea of the problem comes up. Instead of making our nodes $$$(i, x)$$$ represent $$$a_i = x$$$, let's make them $$$a_i \ge x$$$ and try building the graph again.
If $$$a_i = x$$$, then all nodes $$$(i, y)$$$ for $$$y \le x$$$ will be true, and the rest will be false. So if $$$(i, x)$$$ is false, then $$$(i, x + 1)$$$ is false. That will enforce the validity of the nodes themselves.
First, the order. If $$$(i, x)$$$ is true, then $$$(i + 1, x)$$$ is true.
The first type of constraints. $$$a_i \neq x$$$ is basically the same as ($$$a_i < x$$$ or $$$a_i > x$$$). For our conditions, it's rather ((not $$$a_i \ge x$$$) or $$$a_i \ge x + 1$$$).
The second type of constraints. $$$a_i + a_j \le x$$$. Let $$$a_i$$$ be greater than or equal to some $$$y$$$. Then, for this constraint to hold, $$$a_j$$$ should be no greater than $$$x - y$$$. Thus, if $$$(a_i \ge y)$$$ is true, then $$$(a_j \ge x - y + 1)$$$ should be false. Same for $$$i$$$ and $$$j$$$ swapped.
The third type of constraints is similar. $$$a_i + a_j \ge x$$$. Let $$$a_i$$$ be less than or equal to some $$$y$$$. Then, for this constraint to hold, $$$a_j$$$ should be greater than or equal to $$$x - y$$$. Thus, if $$$(a_i \ge y + 1)$$$ is false, then $$$(a_j \ge x - y)$$$ should be true. Same for $$$i$$$ and $$$j$$$ swapped.
And that's it. Solve the 2-SAT and restore the answer. I can advise making not $$$k$$$ but actually $$$k + 2$$$ nodes for $$$a_i \ge 0, 1, \dots, k+1$$$ and force the values to be between $$$1$$$ and $$$k$$$. That will simplify the checks while adding the constraints.
Overall complexity: $$$O((n+m)k)$$$.