Not Assigning (Codeforces 1627C)
Tags: Others, number theory

You are given a tree of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$, with edges numbered from $$$1$$$ to $$$n-1$$$. A tree is a connected undirected graph without cycles. You have to assign integer weights to each edge of the tree, such that the resultant graph is a prime tree.A prime tree is a tree where the weight of every path consisting of one or two edges is prime. A path should not visit any vertex twice. The weight of a path is the sum of edge weights on that path.Consider the graph below. It is a prime tree as the weight of every path of two or less edges is prime. For example, the following path of two edges: $$$2 \to 1 \to 3$$$ has a weight of $$$11 + 2 = 13$$$, which is prime. Similarly, the path of one edge: $$$4 \to 3$$$ has a weight of $$$5$$$, which is also prime.  Print any valid assignment of weights such that the resultant tree is a prime tree. If there is no such assignment, then print $$$-1$$$. It can be proven that if a valid assignment exists, one exists with weights between $$$1$$$ and $$$10^5$$$ as well.

Input: The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains one integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — the number of vertices in the tree.Then, $$$n-1$$$ lines follow. The $$$i$$$-th line contains two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$) denoting that edge number $$$i$$$ is between vertices $$$u$$$ and $$$v$$$. It is guaranteed that the edges form a tree.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case, if a valid assignment exists, then print a single line containing $$$n-1$$$ integers $$$a_1, a_2, \dots, a_{n-1}$$$ ($$$1 \leq a_i \le 10^5$$$), where $$$a_i$$$ denotes the weight assigned to the edge numbered $$$i$$$. Otherwise, print $$$-1$$$.If there are multiple solutions, you may print any.

Note: For the first test case, there are only two paths having one edge each: $$$1 \to 2$$$ and $$$2 \to 1$$$, both having a weight of $$$17$$$, which is prime.  The second test case is described in the statement.It can be proven that no such assignment exists for the third test case.

Sample Inputs:
3
2
1 2
4
1 3
4 3
2 1
7
1 2
1 3
3 4
3 5
6 2
7 2

Sample Outputs:
17
2 5 11
-1

Solution (Python):
from collections import Counter
import sys

def solve():
    n = int(sys.stdin.readline().strip())
    g = [[] for __ in range(n + 1)]
    ans = [-1] * (n - 1)
    bad = False
    for edge in range(n - 1):
        (x, y) = map(int, sys.stdin.readline().strip().split())
        g[x] += [(y, edge)]
        g[y] += [(x, edge)]
        if len(g[x]) > 2 or len(g[y]) > 2:
            bad = True
    if bad:
        print(-1)
        return
    for i in range(1, n + 1):
        if len(g[i]) == 1:
            cur = i
            break
    seen = [False] * (n + 1)
    for p in range(n - 1):
        for (x, edge) in g[cur]:
            if not seen[x]:
                ans[edge] = 3 if p % 2 else 2
                seen[cur] = True
                cur = x
                break
    print(*ans)
if __name__ == '__main__':
    for _ in range(int(sys.stdin.readline())):
        solve()

Solution (Python):
import sys

def solve():
    inp = sys.stdin.readline
    n = int(inp())
    e = [[] for i in range(n + 1)]
    for i in range(n - 1):
        (u, v) = map(int, inp().split())
        e[u].append((v, i))
        e[v].append((u, i))
    s = None
    for i in range(1, n + 1):
        if len(e[i]) == 1:
            s = i
            break
    if s is None:
        print(-1, 'no start')
        return
    c = [11, 2, 5, 2]
    ans = [None] * (n - 1)
    p = -1
    x = s
    for i in range(n - 1):
        if p == -1:
            (v, j) = e[x][0]
            ans[j] = c[i % 4]
        elif len(e[x]) != 2:
            print(-1)
            return
        elif e[x][0][0] == p:
            (v, j) = e[x][1]
            ans[j] = c[i % 4]
        else:
            (v, j) = e[x][0]
            ans[j] = c[i % 4]
        p = x
        x = v
    print(' '.join(map(str, ans)))

def main():
    for i in range(int(sys.stdin.readline())):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin, gettrace
if gettrace():

    def inputi():
        return input()
else:

    def input():
        return next(stdin)[:-1]

    def inputi():
        return stdin.buffer.readline()

def solve(n, e):
    ne = [[] for _ in range(n + 1)]
    for (i, (u, v)) in enumerate(e):
        ne[u].append((i, v))
        ne[v].append((i, u))
    res = [0] * (n - 1)
    for u in range(n):
        if len(ne[u]) == 1:
            break
    pv = 2
    pi = ne[u][0][0]
    res[pi] = 2
    u = ne[u][0][1]
    while True:
        if len(ne[u]) > 2:
            return [-1]
        if len(ne[u]) == 1:
            return res
        for (i, v) in ne[u]:
            if i != pi:
                pv = res[i] = 2 if pv == 3 else 3
                pi = i
                u = v
                break

def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        e = [[int(a) for a in input().split()] for _ in range(n - 1)]
        print(' '.join(map(str, solve(n, e))))
if __name__ == '__main__':
    main()