#P1616F. Tricolor Triangles
-
ID: 7578
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: 10
Uploaded By:
Hydro
Tags> Tricolor Triangles
Description
You are given a simple undirected graph with $n$ vertices and $m$ edges. Edge $i$ is colored in the color $c_i$, which is either $1$, $2$, or $3$, or left uncolored (in this case, $c_i = -1$).
You need to color all of the uncolored edges in such a way that for any three pairwise adjacent vertices $1 \leq a < b < c \leq n$, the colors of the edges $a \leftrightarrow b$, $b \leftrightarrow c$, and $a \leftrightarrow c$ are either pairwise different, or all equal. In case no such coloring exists, you need to determine that.
The first line of input contains one integer $t$ ($1 \leq t \leq 10$): the number of test cases.
The following lines contain the description of the test cases.
In the first line you are given two integers $n$ and $m$ ($3 \leq n \leq 64$, $0 \leq m \leq \min(256, \frac{n(n-1)}{2})$): the number of vertices and edges in the graph.
Each of the next $m$ lines contains three integers $a_i$, $b_i$, and $c_i$ ($1 \leq a_i, b_i \leq n$, $a_i \ne b_i$, $c_i$ is either $-1$, $1$, $2$, or $3$), denoting an edge between $a_i$ and $b_i$ with color $c_i$. It is guaranteed that no two edges share the same endpoints.
For each test case, print $m$ integers $d_1, d_2, \ldots, d_m$, where $d_i$ is the color of the $i$-th edge in your final coloring. If there is no valid way to finish the coloring, print $-1$.
Input
The first line of input contains one integer $t$ ($1 \leq t \leq 10$): the number of test cases.
The following lines contain the description of the test cases.
In the first line you are given two integers $n$ and $m$ ($3 \leq n \leq 64$, $0 \leq m \leq \min(256, \frac{n(n-1)}{2})$): the number of vertices and edges in the graph.
Each of the next $m$ lines contains three integers $a_i$, $b_i$, and $c_i$ ($1 \leq a_i, b_i \leq n$, $a_i \ne b_i$, $c_i$ is either $-1$, $1$, $2$, or $3$), denoting an edge between $a_i$ and $b_i$ with color $c_i$. It is guaranteed that no two edges share the same endpoints.
Output
For each test case, print $m$ integers $d_1, d_2, \ldots, d_m$, where $d_i$ is the color of the $i$-th edge in your final coloring. If there is no valid way to finish the coloring, print $-1$.
Samples
4
3 3
1 2 1
2 3 2
3 1 -1
3 3
1 2 1
2 3 1
3 1 -1
4 4
1 2 -1
2 3 -1
3 4 -1
4 1 -1
3 3
1 2 1
2 3 1
3 1 2
1 2 3
1 1 1
1 2 2 3
-1