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.


-----Examples-----

Input
3
2
1 2
4
1 3
4 3
2 1
7
1 2
1 3
3 4
3 5
6 2
7 2
Output
17
2 5 11
-1


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

Source: codeforces | Difficulty: MEDIUM
Tags: Number theory

Tree algorithms

Graph traversal

Constructive algorithms


Solutions:
def solve():
	n = int(input())
	T = [[] for _ in range(n)]
	for i in range(n - 1):
		(u, v) = [int(x) - 1 for x in input().split()]
		T[u].append((v, i))
		T[v].append((u, i))
	start = None
	for (idx, edges) in enumerate(T):
		if len(edges) > 2:
			return '-1'
		if len(edges) == 1:
			start = idx
	ret = [None] * (n - 1)
	val = 2
	p = start
	parent = -1
	while True:
		found = False
		for (q, idx) in T[p]:
			if q != parent:
				found = True
				ret[idx] = val
				parent = p
				p = q
				break
		val = 2 if val == 3 else 3
		if not found:
			break
	return ' '.join([str(x) for x in ret])
t = int(input())
for _ in range(t):
	print(solve())


import sys
input = sys.stdin.readline

def solve(n, adj):
	node = -1
	for v in range(n):
		if len(adj[v]) > 2:
			return [-1]
		if len(adj[v]) == 1:
			node = v
	vis = [False for _ in range(n)]
	ans = [0 for _ in range(n - 1)]
	ans[adj[node][0][1]] = 2
	prev = node
	node = adj[node][0][0]
	flag = True
	while len(adj[node]) > 1:
		(nxt, pos) = (0, 0)
		if adj[node][0][0] == prev:
			(nxt, pos) = adj[node][1]
		else:
			(nxt, pos) = adj[node][0]
		if flag:
			ans[pos] = 3
		else:
			ans[pos] = 2
		flag = not flag
		prev = node
		node = nxt
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	adj = [[] for _ in range(n)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u - 1].append((v - 1, i))
		adj[v - 1].append((u - 1, i))
	print(*solve(n, adj))


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	n = int(input())
	graph = [[] for _ in range(n + 1)]
	edges = [-1] * (n - 1)
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		graph[u].append((v, i))
		graph[v].append((u, i))
	if max([len(neighbors) for neighbors in graph]) > 2:
		print(-1)
		continue
	(prev, cur) = (None, 1)
	while len(graph[cur]) != 1:
		cur += 1
	for r in range(n - 1):
		for (x, i) in graph[cur]:
			if x != prev:
				edges[i] = [2, 3][r % 2]
				(prev, cur) = (cur, x)
				break
	print(*edges)


for _ in range(int(input())):
	n = int(input())
	graph = [[] for _ in range(n + 1)]
	edges = [-1] * (n - 1)
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		graph[u].append((v, i))
		graph[v].append((u, i))
	if max([len(neighbors) for neighbors in graph]) > 2:
		print(-1)
		continue
	(prev, cur) = (None, 1)
	while len(graph[cur]) != 1:
		cur += 1
	for r in range(n - 1):
		for (x, i) in graph[cur]:
			if x != prev:
				edges[i] = [2, 3][r % 2]
				(prev, cur) = (cur, x)
				break
	print(*edges)


import math, re

def fastlist():
	return list(map(int, input().split()))

def fastint():
	return int(input())

def solve():
	n = fastint()
	res = [0] * (n - 1)
	ver = [[] for _ in range(n)]
	for i in range(n - 1):
		(u, v) = fastlist()
		ver[u - 1] += [(v - 1, i)]
		ver[v - 1] += [(u - 1, i)]
	for i in range(n):
		if len(ver[i]) == 1:
			start = i
			break
	(cur, prev) = (start, -1)
	for i in range(n - 1):
		if len(ver[cur]) > 2:
			print(-1)
			return
		for (j, x) in ver[cur]:
			if j != prev:
				res[x] = ['2', '3'][i % 2]
				(cur, prev) = (j, cur)
				break
	print(*res)
t = int(input())
for _ in range(t):
	solve()


from platform import node
from sys import intern

def solve():
	n = int(input())
	node___neighs = [[] for _ in range(n)]
	edges = []
	for _ in range(n - 1):
		(u, v) = (int(x) - 1 for x in input().split())
		if v < u:
			(u, v) = (v, u)
		edges.append((u, v))
		node___neighs[u].append(v)
		node___neighs[v].append(u)
	start_node = None
	for node in range(n):
		if len(node___neighs[node]) > 2:
			print(-1)
			return
		if len(node___neighs[node]) == 1:
			start_node = node
	node___is_visited = [False for _ in range(n)]
	edge___weight = {}
	const_prime = 5
	curr_weight = 2
	stack = [start_node]
	while stack:
		curr_node = stack.pop()
		node___is_visited[curr_node] = True
		for neigh in node___neighs[curr_node]:
			if not node___is_visited[neigh]:
				edge = (curr_node, neigh)
				if neigh < curr_node:
					edge = (neigh, curr_node)
				edge___weight[edge] = curr_weight
				stack.append(neigh)
		curr_weight = const_prime - curr_weight
	ans = [edge___weight[edge] for edge in edges]
	print(*ans, sep=' ', end='\n')
for _ in range(int(input())):
	solve()


T = int(input())
for _ in range(T):
	n = int(input())
	to = [[] for _ in range(n)]
	a = [0] * n
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		a[u] += 1
		a[v] += 1
		to[u].append((v, i))
		to[v].append((u, i))
	if max(a) > 2:
		print(-1)
		continue
	cur = a.index(1)
	last = -1
	res = [0] * (n - 1)
	for i in range(n - 1):
		for (v, ind) in to[cur]:
			if v != last:
				res[ind] = 2 if i % 2 == 0 else 3
				last = cur
				cur = v
				break
	print(*res)


for _ in range(int(input())):
	n = int(input())
	cnt = [0] * (n + 1)
	graph = [[] for i in range(n + 1)]
	edges = [list(map(int, input().split())) for i in range(n - 1)]
	w = [0] * (n - 1)
	for i in range(n - 1):
		edge = edges[i]
		cnt[edge[0]] += 1
		cnt[edge[1]] += 1
		graph[edge[0]].append((edge[1], i))
		graph[edge[1]].append((edge[0], i))
	if max(cnt) > 2:
		print(-1)
		continue
	v = cnt.index(1)
	curr = 2
	used = [0] * (n + 1)
	used[v] = 1
	for i in range(n - 1):
		u = graph[v][0][0]
		k = 0
		if used[u]:
			u = graph[v][1][0]
			k = 1
		w[graph[v][k][1]] = curr
		curr = 5 - curr
		v = u
		used[v] = 1
	print(*w)


import sys
input = sys.stdin.readline
t = int(input())
out = []
for _ in range(t):
	n = int(input())
	cons = [[] for _ in range(n)]
	isGood = True
	for i in range(n - 1):
		(a, b) = [int(x) - 1 for x in input().split()]
		cons[a].append([b, i])
		cons[b].append([a, i])
		if len(cons[a]) == 3 or len(cons[b]) == 3:
			isGood = False
	if not isGood:
		out.append('-1\n')
		continue
	for i in range(len(cons)):
		if len(cons[i]) == 1:
			start = i
			break
	weights = [0] * (n - 1)
	next_ = 2
	search = [start]
	while len(search) > 0:
		node = search.pop(-1)
		for (child, ind) in cons[node]:
			if weights[ind] == 0:
				weights[ind] = next_
				search.append(child)
				next_ = 5 - next_
	strWeights = ''
	for x in weights:
		strWeights += str(x) + ' '
	out.append(strWeights + '\n')
print(''.join(out))


import sys, collections

def solve(n, loc, conn):
	for u in conn:
		if len(conn[u]) > 2:
			return []
	res = [-1] * (n - 1)
	level = {[u for u in conn if len(conn[u]) == 1][0]}
	visit = level.copy()
	value = 2
	while level:
		nextlevel = set()
		for prev in level:
			for curr in conn[prev]:
				if curr not in visit:
					if (prev, curr) in loc:
						res[loc[prev, curr]] = value
					else:
						res[loc[curr, prev]] = value
					nextlevel.add(curr)
					visit.add(curr)
		level = nextlevel
		value = 5 - value
	return res
input = sys.stdin.readline
t = int(input()[:-1])
for _ in range(t):
	n = int(input()[:-1])
	loc = {}
	conn = collections.defaultdict(set)
	for i in range(n - 1):
		(u, v) = [int(s) for s in input()[:-1].split()]
		loc[u, v] = i
		conn[u].add(v)
		conn[v].add(u)
	res = solve(n, loc, conn)
	if res == []:
		print(-1)
	else:
		print(*res)


t = int(input())
for _ in range(t):
	n = int(input())
	possible = True
	al = [[] for i in range(n)]
	edgenum = {}
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		al[a].append(b)
		al[b].append(a)
		edgenum[a, b] = i
		edgenum[b, a] = i
	for i in range(n):
		if len(al[i]) > 2:
			possible = False
			break
	if not possible:
		print(-1)
	else:
		startnode = 0
		for i in range(n - 1):
			if len(al[i]) < 2:
				startnode = i
				break
		l = [0 for i in range(n - 1)]
		done = set()
		for x in range(n - 1):
			nextnode = al[startnode][0]
			if nextnode in done:
				nextnode = al[startnode][1]
			i = edgenum[startnode, nextnode]
			l[i] = 2 + x % 2
			done.add(startnode)
			startnode = nextnode
		print(*l)


import sys
input = sys.stdin.readline
num_test_cases = int(input())
for test_case_ittr in range(num_test_cases):
	num_vertices = int(input())
	edges = []
	possible = True
	neighbors = dict()
	for i in range(num_vertices - 1):
		(a, b) = [int(x) for x in input().split()]
		edges += [(a, b)]
		if a not in neighbors:
			neighbors[a] = {b}
		else:
			neighbors[a].add(b)
		if len(neighbors[a]) > 2:
			possible = False
		if b not in neighbors:
			neighbors[b] = {a}
		else:
			neighbors[b].add(a)
		if len(neighbors[b]) > 2:
			possible = False
	if not possible:
		print(-1)
		continue
	leaf = None
	for node in neighbors:
		if len(neighbors[node]) == 1:
			leaf = node
			break
	edge_weights = dict()
	node = leaf
	prev = None
	weight = 2
	for j in range(num_vertices - 1):
		next_node = list(neighbors[node] - {prev})[0]
		edge_weights[node, next_node] = edge_weights[next_node, node] = weight
		(prev, node) = (node, next_node)
		if j & 1:
			weight -= 1
		else:
			weight += 1
	print(*[edge_weights[edge] for edge in edges])


import sys, collections

def solve(n, loc, conn, su, sv):
	for u in conn:
		if len(conn[u]) > 2:
			return [-1]
	res = [-1] * (n - 1)
	res[loc[su, sv]] = 2
	level = {su, sv}
	value = 2
	while level:
		nextlevel = set()
		value = 5 - value
		for prev in level:
			for curr in conn[prev]:
				if (prev, curr) in loc:
					if res[loc[prev, curr]] != -1:
						continue
					res[loc[prev, curr]] = value
					nextlevel.add(curr)
				else:
					if res[loc[curr, prev]] != -1:
						continue
					res[loc[curr, prev]] = value
					nextlevel.add(curr)
		level = nextlevel
	return res
input = sys.stdin.readline
t = int(input()[:-1])
for _ in range(t):
	n = int(input()[:-1])
	loc = {}
	conn = collections.defaultdict(set)
	for i in range(n - 1):
		(u, v) = [int(part) for part in input()[:-1].split()]
		loc[u, v] = i
		conn[u].add(v)
		conn[v].add(u)
	res = solve(n, loc, conn, u, v)
	if res[0] == -1:
		print(-1)
	else:
		for val in res:
			print(val, end=' ')
		print('\n', end='')


for _ in range(int(input())):
	n = int(input())
	g = [[] for _ in range(n)]
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		g[a - 1].append([b - 1, i])
		g[b - 1].append([a - 1, i])
	for i in range(n):
		if len(g[i]) > 2:
			print(-1)
			break
	else:
		l = [0] * (n - 1)
		ord = []
		for i in range(n):
			if len(g[i]) == 1:
				ord.append(g[i][0][1])
				start = g[g[i][0][0]]
				break
		while len(start) == 2:
			for j in start:
				if j[1] != ord[-1]:
					ord.append(j[1])
					start = g[j[0]]
					break
		for i in range(len(ord)):
			if i % 2 == 0:
				l[ord[i]] = 2
			else:
				l[ord[i]] = 3
		print(*l)


import sys, bisect, math
from collections import deque, Counter
input = lambda : sys.stdin.readline().strip()
ceil = lambda x: math.ceil(x)
mod = 10 ** 9 + 7

def solve():
	n = int(input())
	three = [True] * (n + 1)
	two = [True] * (n + 1)
	visited = [False] * (n + 1)
	edges = []
	graph = {i: set() for i in range(1, n + 1)}
	index = {}
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		edges.append([u, v])
		graph[u].add(v)
		graph[v].add(u)
		(u, v) = (min(u, v), max(u, v))
		index[u, v] = i
	ans = [0] * (n - 1)
	queue = deque()
	queue.append(1)
	visited[1] = True
	while len(queue) != 0:
		x = queue.popleft()
		for i in graph[x]:
			if not visited[i]:
				visited[i] = True
				queue.append(i)
				if two[i] and two[x]:
					ans[index[min(i, x), max(i, x)]] = '2'
					two[i] = two[x] = False
				elif three[i] and three[x]:
					ans[index[min(i, x), max(i, x)]] = '3'
					three[i] = three[x] = False
				else:
					return -1
	return ' '.join(ans)
t = 1
t = int(input())
for _ in range(t):
	print(solve())


for _ in range(int(input())):
	n = int(input())
	q = {}
	for i in range(1, n + 1):
		q[i] = set()
	l = []
	r = {}
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		l += [(a, b)]
		r[a, b] = 0
		q[a].add(b)
		q[b].add(a)
	t = 1
	k = 0
	for i in q:
		if len(q[i]) > 2:
			print(-1)
			t = 0
			break
		elif len(q[i]) == 1:
			k = i
	if t:
		v = {}
		j = 0
		for i in range(1, n + 1):
			v[i] = 1
		v[k] = 0
		for _ in range(n - 1):
			for i in q[k]:
				if v[i]:
					v[i] = 0
					if (i, k) in r:
						r[i, k] = j + 2
					else:
						r[k, i] = j + 2
					k = i
			j = 1 - j
		a = [0] * (n - 1)
		for i in range(n - 1):
			a[i] = r[l[i]]
		print(*a)


def dfs(graph, start):
	result = dict()
	value = 2
	for el in graph[start]:
		visited = {start, el}
		result[tuple(sorted([start, el]))] = value
		last = el
		while True:
			value = 3 if value == 2 else 2
			neighbours = graph[last] - visited
			if len(neighbours) == 0:
				break
			elem = neighbours.pop()
			result[tuple(sorted([last, elem]))] = value
			visited.add(elem)
			last = elem
		value = 3
	return result

def solve():
	for i in range(int(input())):
		count = dict()
		pairs = []
		graph = dict()
		br = 0
		for j in range(int(input()) - 1):
			(a, b) = list(sorted(map(int, input().split())))
			pairs.append((a, b))
			graph[a] = graph.get(a, set())
			graph[a].add(b)
			graph[b] = graph.get(b, set())
			graph[b].add(a)
			count[a] = count.get(a, 0) + 1
			count[b] = count.get(b, 0) + 1
			if count[a] == 3 or count[b] == 3:
				br = -1
		if br == -1:
			print(br)
			continue
		result = dfs(graph, pairs[0][0])
		for pair in pairs:
			print(result[pair], end=' ')
		print()
solve()


t = int(input())
while t:
	t -= 1
	n = int(input())
	d = {}
	ans = {}
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		if u not in d:
			d[u] = []
		if v not in d:
			d[v] = []
		d[u].append(v)
		d[v].append(u)
		ans[u, v] = 0
	r = 0
	key = 1
	for i in d:
		if len(d[i]) == 1:
			key = i
		if len(d[i]) >= 3:
			r = 1
			break
	if r == 1:
		print(-1)
		continue
	visited = [0 for i in range(n + 1)]
	st = []
	st.append((0, key))
	f = -1
	while st:
		key = st[-1]
		i = st[-1][1]
		st.pop()
		if visited[i] == 1:
			continue
		if visited[i] == 0 and f != -1:
			if f == 0:
				f = 1
				if key not in ans:
					ans[key[1], key[0]] = 2
				else:
					ans[key] = 2
			else:
				f = 0
				if key not in ans:
					ans[key[1], key[0]] = 3
				else:
					ans[key] = 3
		if f == -1:
			f = 0
		for e in d[i]:
			if visited[e] == 0:
				st.append((i, e))
		visited[i] = 1
	for i in ans:
		if ans[i] > 0:
			print(ans[i], end=' ')
	print()


for t in range(int(input())):
	n = int(input())
	S = [[int(i) for i in input().split()] for j in range(n - 1)]
	d = dict()
	for i in range(n - 1):
		d[tuple(S[i])] = 0
	if len(S) == 1:
		print(2)
	else:
		A = [[] for i in range(n)]
		flag = 1
		for i in range(n - 1):
			(a, b) = S[i]
			A[a - 1].append(b - 1)
			A[b - 1].append(a - 1)
			if len(A[a - 1]) > 2 or len(A[b - 1]) > 2:
				flag = 0
				break
		if flag == 0:
			print(-1)
		else:
			B = list()
			for i in range(n):
				if len(A[i]) == 1:
					B.append(i)
			start = B[0]
			end = B[1]
			C = [2, 3]
			flag = 0
			e1 = start
			e2 = A[start][0]
			for i in range(n - 1):
				if (e1 + 1, e2 + 1) in d:
					d[tuple([e1 + 1, e2 + 1])] = C[flag]
				elif (e2 + 1, e1 + 1) in d:
					d[tuple([e2 + 1, e1 + 1])] = C[flag]
				if i != n - 2:
					A[e2].remove(e1)
					e1 = e2
					e2 = A[e1][0]
				flag = 0 if flag else 1
			ans = list()
			for i in range(n - 1):
				ans.append(d[tuple(S[i])])
			print(*ans)


from collections import deque
from functools import partial
from typing import Deque, List, Literal, Optional, Set, TYPE_CHECKING

class Edge:
	__slots__ = ('points', 'weight')
	if TYPE_CHECKING:
		points: Set[int]
		weight: Optional[int]

	def __init__(self, points: Set[int]) -> None:
		self.points = points
		self.weight = None

def set_weight(edge: Edge, value: Literal[2, 3]) -> None:
	if edge.weight is not None:
		return
	edge.weight = value
	for point in edge.points:
		for e in nodes[point]:
			functions.append(partial(set_weight, e, 5 - edge.weight))
for _ in range(int(input())):
	n = int(input())
	nodes: List[Set[Edge]] = [set() for _ in range(n)]
	edges: List[Edge] = []
	for index in range(n - 1):
		(u, v) = [int(i) - 1 for i in input().split()]
		edge = Edge({u, v})
		nodes[u].add(edge)
		nodes[v].add(edge)
		edges.append(edge)
	if any(map(lambda node: len(node) > 2, nodes)):
		print(-1)
	else:
		functions: Deque[partial] = deque([partial(set_weight, edges[0], 2)])
		while functions:
			func = functions.popleft()
			func()
		print(*[edge.weight for edge in edges])


from collections import defaultdict, deque
t = int(input())
for _ in range(t):
	n = int(input())
	edge = []
	graph = defaultdict(list)
	for i in range(n - 1):
		ab = input().split(' ')
		graph[int(ab[0])].append([int(ab[1]), i])
		graph[int(ab[1])].append([int(ab[0]), i])
		edge.append([int(ab[0]), int(ab[1]), i])
	finded = False
	for i in graph:
		if len(graph[i]) > 2:
			print(-1)
			finded = True
			break
	if finded:
		continue
	edge_graph = defaultdict(list)
	for i in graph:
		if len(graph[i]) < 2:
			continue
		edge1 = graph[i][0][1]
		edge2 = graph[i][1][1]
		if edge2 not in edge_graph[edge1]:
			edge_graph[edge1].append(edge2)
		if edge1 not in edge_graph[edge2]:
			edge_graph[edge2].append(edge1)
	ans = [0] * (n - 1)
	ans[0] = 2
	q = deque()
	q.append((0, 2))
	visited = defaultdict(int)
	while q:
		ele = q.popleft()
		if visited[ele[0]] == 1:
			continue
		visited[ele[0]] = 1
		ansput = 2
		if ele[1] == 2:
			ansput = 3
		for i in edge_graph[ele[0]]:
			if visited[i] == 1:
				continue
			q.append((i, ansput))
			ans[i] = ansput
	for i in range(len(ans)):
		ans[i] = str(ans[i])
	print(' '.join(ans))