CF1616F.Tricolor Triangles

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