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