CF1815F OH NO1 (-2-3-4)

You are given an undirected graph with $ n $ vertices and $ 3m $ edges. The graph may contains multi-edges, but do not contain self loops. The graph satisfy the following property: the given edges can be divided into $ m $ groups of $ 3 $ , such that each group is a triangle. A triangle are three edges $ (a,b) $ , $ (b,c) $ and $ (c,a) $ , for some three distinct vertices $ a,b,c $ ( $ 1 \leq a,b,c \leq n $ ). Initially, each vertex $ v $ has a non-negative integer weight $ a_v $ . For every edge $ (u,v) $ in the graph, you should perform the following operation exactly once: - Choose an integer $ x $ between $ 1 $ and $ 4 $ . Then increase both $ a_u $ and $ a_v $ by $ x $ . After performing all operations, the following requirement should be satisfied: if $ u $ and $ v $ are connected by an edge, then $ a_u \ne a_v $ . It can be proven this is always possible under the constraints of the task. Output a way to do so, by outputting the choice of $ x $ for each edge. It is easy to see that the order of operations do not matter. If there are multiple valid answers, output any.

N/A

N/A

In the first test case, the initial weights are $ [0,0,0,0] $ . We have added values as follows: - Added $ 2 $ to vertices $ 1 $ and $ 2 $ - Added $ 1 $ to vertices $ 1 $ and $ 3 $ - Added $ 3 $ to vertices $ 2 $ and $ 3 $ The final weights are $ [3,5,4,0] $ . The output is valid because $ a_1 \neq a_2 $ , $ a_1 \neq a_3 $ , $ a_2 \neq a_3 $ , and that all chosen values are between $ 1 $ and $ 4 $ . In the second test case, the initial weights are $ [0,0,0,0,0] $ . The weights after the operations are $ [12,5,6,7,6] $ . The output is valid because $ a_1 \neq a_2 $ , $ a_1 \neq a_3 $ , $ a_2 \neq a_3 $ , and that $ a_1 \neq a_4 $ , $ a_1 \neq a_5 $ , $ a_4 \neq a_5 $ , and that all chosen values are between $ 1 $ and $ 4 $ . In the third test case, the initial weights are $ [3,4,5,6] $ . The weights after the operations are $ [19,16,17,20] $ , so all final weights are distinct, which means no two adjacent vertices have the same weight.