Tricolor Triangles (Codeforces 1616F)
Tags: Math, matrices

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.

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


Sample Inputs:
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

Sample Outputs:
1 2 3 
1 1 1 
1 2 2 3 
-1

Solution (Python):
import sys
I = lambda : [*map(int, sys.stdin.readline().split())]

class Equation:

    def __init__(self, variables, val, index, inclusion):
        self.coeffs = {}
        for guy in variables:
            self.coeffs[guy] = 1
            inclusion[guy].add(index)
        self.val = val
        self.index = index

    def add(self, other, inclusion):
        self.val += other.val
        for guy in other.coeffs:
            if guy in self.coeffs:
                x = (self.coeffs[guy] + other.coeffs[guy]) % 3
                if x == 0:
                    del self.coeffs[guy]
                    inclusion[guy].remove(self.index)
                else:
                    self.coeffs[guy] = x
            else:
                self.coeffs[guy] = other.coeffs[guy]
                inclusion[guy].add(self.index)

    def sub(self, other, inclusion):
        self.val -= other.val
        for guy in other.coeffs:
            if guy in self.coeffs:
                if self.coeffs[guy] == other.coeffs[guy]:
                    del self.coeffs[guy]
                    inclusion[guy].remove(self.index)
                else:
                    self.coeffs[guy] = (self.coeffs[guy] - other.coeffs[guy]) % 3
            else:
                self.coeffs[guy] = 3 - other.coeffs[guy]
                inclusion[guy].add(self.index)
(t,) = I()
for _ in range(t):
    (n, m) = I()
    neigh = [{} for i in range(n)]
    colors = []
    for i in range(m):
        (a, b, c) = I()
        a -= 1
        b -= 1
        if c > 0:
            c -= 1
        colors.append(c)
        if a < b:
            neigh[a][b] = (c, i)
        else:
            neigh[b][a] = (c, i)
    triangles = []
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if j in neigh[i] and k in neigh[i] and (k in neigh[j]):
                    triangles.append((i, j, k))
    equations = []
    l = 0
    inclusion = [set() for i in range(m)]
    for (i, j, k) in triangles:
        (c1, i1) = neigh[i][j]
        (c2, i2) = neigh[i][k]
        (c3, i3) = neigh[j][k]
        variables = []
        val = 0
        if c1 == -1:
            variables.append(i1)
        else:
            val -= c1
        if c2 == -1:
            variables.append(i2)
        else:
            val -= c2
        if c3 == -1:
            variables.append(i3)
        else:
            val -= c3
        equations.append(Equation(variables, val % 3, l, inclusion))
        l += 1
    pivots = set()
    pivotvars = set()
    for i in range(m):
        add = False
        for j in inclusion[i] - pivots:
            pivot = j
            add = True
            pivotvars.add(i)
            l = list(inclusion[i])
            main = equations[j]
            coeff = main.coeffs[i]
            for k in l:
                if k != j:
                    o = equations[k].coeffs[i]
                    if o == coeff:
                        equations[k].sub(main, inclusion)
                    else:
                        equations[k].add(main, inclusion)
            break
        if add:
            pivots.add(pivot)
    for guy in equations:
        if len(guy.coeffs) == 0 and guy.val % 3 != 0:
            print(-1)
            break
    else:
        for i in range(m - 1, -1, -1):
            if i not in pivotvars and colors[i] == -1:
                colors[i] = 0
            elif i in pivotvars:
                for j in inclusion[i]:
                    eq = equations[j]
                    val = eq.val
                    for v in eq.coeffs:
                        if v != i:
                            val -= eq.coeffs[v] * colors[v]
                    if eq.coeffs[i] == 1:
                        colors[i] = val % 3
                    else:
                        colors[i] = -val % 3
        colors = [guy + 1 for guy in colors]
        print(*colors)

Solution (Python):
from itertools import combinations
from collections import defaultdict
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def F1(A, B, C, D):
    AD = A ^ D
    return (AD ^ B | A ^ C, AD & (B ^ C))

def F2(A, B, C, D):
    AC = A ^ C
    return (AC | B ^ D, (AC ^ D) & (B ^ C))

def flip_bit(a, i):
    a[i // l] ^= 1 << i % l

def Gauss(a, b, n, m):
    if n == 0:
        return (2, [0] * m)
    where = [-1] * m
    (row, col) = (0, 0)
    while col < m and row < n:
        (t1, t2) = divmod(col, l)
        for i in range(row, n):
            if a[i][t1] >> t2 & 1 or b[i][t1] >> t2 & 1:
                (a[i], a[row]) = (a[row], a[i])
                (b[i], b[row]) = (b[row], b[i])
                break
        if not a[row][t1] >> t2 & 1 and (not b[row][t1] >> t2 & 1):
            col += 1
            continue
        where[col] = row
        for i in range(n):
            if i == row:
                continue
            (x1, x2) = (a[i][t1] >> t2 & 1, b[i][t1] >> t2 & 1)
            (y1, y2) = (a[row][t1] >> t2 & 1, b[row][t1] >> t2 & 1)
            cc = (x1 + x2) * (y1 + y2) % 3
            if cc == 0:
                continue
            F = F1 if cc == 2 else F2
            for k in range(t1, U):
                (a[i][k], b[i][k]) = F(a[i][k], b[i][k], a[row][k], b[row][k])
        (col, row) = (col + 1, row + 1)
    ans = [0] * m
    (t1, t2) = divmod(m, l)
    for i in range(m):
        W = where[i]
        if W != -1:
            (t3, t4) = divmod(i, l)
            (x1, x2) = (a[W][t1] >> t2 & 1, b[W][t1] >> t2 & 1)
            (y1, y2) = (a[W][t3] >> t4 & 1, b[W][t3] >> t4 & 1)
            ans[i] = (x1 + x2) * (y1 + y2) % 3
    for i in range(n):
        sm = 0
        for j in range(m):
            (t3, t4) = divmod(j, l)
            sm += ((a[i][t3] >> t4 & 1) + (b[i][t3] >> t4 & 1)) * ans[j]
        if (sm - (a[i][t1] >> t2 & 1) - (b[i][t1] >> t2 & 1)) % 3 != 0:
            return (0, [-1] * m)
    if -1 in where:
        return (2, ans)
    return (1, ans)
T = int(input())
for _ in range(T):
    (n, m) = [int(i) for i in input().split()]
    (l, U) = (63, m // 63 + 1)
    G = defaultdict(list)
    edges_back = {}
    colors = [0] * m
    for k in range(m):
        (a, b, c) = [int(i) for i in input().split()]
        G[a] += [(b, c)]
        G[b] += [(a, c)]
        edges_back[a, b] = (k, c)
        edges_back[b, a] = (k, c)
        colors[k] = c
    ans = set()
    for n1 in range(1, n + 1):
        neibs = G[n1]
        for ((n2, c12), (n3, c13)) in combinations(neibs, 2):
            if (n2, n3) in edges_back:
                row = [[0] * U, [0] * U]
                (k12, _) = edges_back[n1, n2]
                (k13, _) = edges_back[n1, n3]
                (k23, c23) = edges_back[n2, n3]
                last = 0
                for (k, c) in ((k12, c12), (k13, c13), (k23, c23)):
                    if c != -1:
                        last -= c
                    else:
                        flip_bit(row[0], k)
                last %= 3
                if last == 1:
                    flip_bit(row[0], m)
                elif last == 2:
                    flip_bit(row[0], m)
                    flip_bit(row[1], m)
                ans.add(tuple((tuple(x) for x in row)))
    (mat1, mat2) = ([], [])
    for (x, y) in ans:
        mat1 += [list(x)]
        mat2 += [list(y)]
    ans = Gauss(mat1, mat2, len(mat1), m)
    if ans[0] == 0:
        out = [-1]
    else:
        out = []
        for i in range(m):
            if colors[i] != -1:
                out += [colors[i]]
            elif ans[1][i] == 0:
                out += [3]
            else:
                out += [ans[1][i]]
    print(' '.join((str(x) for x in out)))

Solution (Python):
from itertools import combinations
from collections import defaultdict
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def F1(A, B, C, D):
    E = A & D ^ B & C
    return (A ^ C ^ E ^ B & D, B ^ D ^ E ^ A & C)

def F2(A, B, C, D):
    E = A & C ^ B & D
    return (A ^ D ^ E ^ B & C, B ^ C ^ E ^ A & D)

def flip_bit(a, i):
    a[i // l] ^= 1 << i % l

def Gauss(a, b, n, m):
    if n == 0:
        return (2, [0] * m)
    where = [-1] * m
    (row, col) = (0, 0)
    while col < m and row < n:
        (t1, t2) = divmod(col, l)
        for i in range(row, n):
            if a[i][t1] >> t2 & 1 or b[i][t1] >> t2 & 1:
                (a[i], a[row]) = (a[row], a[i])
                (b[i], b[row]) = (b[row], b[i])
                break
        if not a[row][t1] >> t2 & 1 and (not b[row][t1] >> t2 & 1):
            col += 1
            continue
        where[col] = row
        for i in range(n):
            if i == row:
                continue
            (x1, x2) = (a[i][t1] >> t2 & 1, b[i][t1] >> t2 & 1)
            (y1, y2) = (a[row][t1] >> t2 & 1, b[row][t1] >> t2 & 1)
            cc = (x1 - x2) * (y1 - y2) % 3
            if cc == 0:
                continue
            F = F1 if cc == 2 else F2
            for k in range(t1, U):
                (a[i][k], b[i][k]) = F(a[i][k], b[i][k], a[row][k], b[row][k])
        (col, row) = (col + 1, row + 1)
    ans = [0] * m
    (t1, t2) = divmod(m, l)
    for i in range(m):
        W = where[i]
        if W != -1:
            (t3, t4) = divmod(i, l)
            (x1, x2) = (a[W][t1] >> t2 & 1, b[W][t1] >> t2 & 1)
            (y1, y2) = (a[W][t3] >> t4 & 1, b[W][t3] >> t4 & 1)
            ans[i] = (x1 - x2) * (y1 - y2) % 3
    for i in range(n):
        sm = 0
        for j in range(m):
            (t3, t4) = divmod(j, l)
            sm += ((a[i][t3] >> t4 & 1) - (b[i][t3] >> t4 & 1)) * ans[j]
        if (sm - (a[i][t1] >> t2 & 1) + (b[i][t1] >> t2 & 1)) % 3 != 0:
            return (0, [-1] * m)
    if -1 in where:
        return (2, ans)
    return (1, ans)
T = int(input())
for _ in range(T):
    (n, m) = [int(i) for i in input().split()]
    (l, U) = (63, m // 63 + 1)
    G = defaultdict(list)
    edges_back = {}
    colors = [0] * m
    for k in range(m):
        (a, b, c) = [int(i) for i in input().split()]
        G[a] += [(b, c)]
        G[b] += [(a, c)]
        edges_back[a, b] = (k, c)
        edges_back[b, a] = (k, c)
        colors[k] = c
    ans = set()
    for n1 in range(1, n + 1):
        neibs = G[n1]
        for ((n2, c12), (n3, c13)) in combinations(neibs, 2):
            if (n2, n3) in edges_back:
                row = [[0] * U, [0] * U]
                (k12, _) = edges_back[n1, n2]
                (k13, _) = edges_back[n1, n3]
                (k23, c23) = edges_back[n2, n3]
                last = 0
                for (k, c) in ((k12, c12), (k13, c13), (k23, c23)):
                    if c != -1:
                        last -= c
                    else:
                        flip_bit(row[0], k)
                last %= 3
                if last == 1:
                    flip_bit(row[0], m)
                elif last == 2:
                    flip_bit(row[1], m)
                ans.add(tuple((tuple(x) for x in row)))
    (mat1, mat2) = ([], [])
    for (x, y) in ans:
        mat1 += [list(x)]
        mat2 += [list(y)]
    ans = Gauss(mat1, mat2, len(mat1), m)
    if ans[0] == 0:
        out = [-1]
    else:
        out = []
        for i in range(m):
            if colors[i] != -1:
                out += [colors[i]]
            elif ans[1][i] == 0:
                out += [3]
            else:
                out += [ans[1][i]]
    print(' '.join((str(x) for x in out)))