Problem: There are n railway stations in Berland. They are connected to each other by n-1 railway sections. The railway network is connected, i.e. can be represented as an undirected tree.

You have a map of that network, so for each railway section you know which stations it connects.

Each of the n-1 sections has some integer value of the scenery beauty. However, these values are not marked on the map and you don't know them. All these values are from 1 to 10^6 inclusive.

You asked m passengers some questions: the j-th one told you three values:

  * his departure station a_j; 
  * his arrival station b_j; 
  * minimum scenery beauty along the path from a_j to b_j (the train is moving along the shortest path from a_j to b_j). 



You are planning to update the map and set some value f_i on each railway section — the scenery beauty. The passengers' answers should be consistent with these values.

Print any valid set of values f_1, f_2, ..., f_{n-1}, which the passengers' answer is consistent with or report that it doesn't exist.

Input

The first line contains a single integer n (2 ≤ n ≤ 5000) — the number of railway stations in Berland.

The next n-1 lines contain descriptions of the railway sections: the i-th section description is two integers x_i and y_i (1 ≤ x_i, y_i ≤ n, x_i ≠ y_i), where x_i and y_i are the indices of the stations which are connected by the i-th railway section. All the railway sections are bidirected. Each station can be reached from any other station by the railway.

The next line contains a single integer m (1 ≤ m ≤ 5000) — the number of passengers which were asked questions. Then m lines follow, the j-th line contains three integers a_j, b_j and g_j (1 ≤ a_j, b_j ≤ n; a_j ≠ b_j; 1 ≤ g_j ≤ 10^6) — the departure station, the arrival station and the minimum scenery beauty along his path.

Output

If there is no answer then print a single integer -1.

Otherwise, print n-1 integers f_1, f_2, ..., f_{n-1} (1 ≤ f_i ≤ 10^6), where f_i is some valid scenery beauty along the i-th railway section.

If there are multiple answers, you can print any of them.

Examples

Input


4
1 2
3 2
3 4
2
1 2 5
1 3 3


Output


5 3 5


Input


6
1 2
1 6
3 1
1 5
4 1
4
6 1 3
3 4 1
6 5 2
1 2 5


Output


5 3 1 2 1 


Input


6
1 2
1 6
3 1
1 5
4 1
4
6 1 1
3 4 3
6 5 3
1 2 4


Output


-1

Solution (in PYTHON3):

Solution:
import sys
from operator import itemgetter
readline = sys.stdin.readline

def parorder(Edge, p):
    N = len(Edge)
    par = [0]*N
    par[p] = -1
    stack = [p]
    order = []
    visited = set([p])
    ast = stack.append
    apo = order.append
    Ei = [None]*N
    while stack:
        vn = stack.pop()
        apo(vn)
        for vf, num in Edge[vn]:
            if vf in visited:
                continue
            Ei[vf] = num
            visited.add(vf)
            par[vf] = vn
            ast(vf)
    return par, order, Ei

def lca(u, v):
    if dist[u] > dist[v]:
        u, v = v, u
    
    ddif = dist[v] - dist[u]
    for i in range(ddif.bit_length()):
        if (1<<i)&ddif:
            v = D[i][v]
    
    if u != v:
        for cnt in range(dist[u].bit_length()-1, -1, -1):
            if D[cnt][u] != D[cnt][v]:
                u = D[cnt][u]
                v = D[cnt][v]
        u = P[u]
    return u

def update(ou, ov, x):
    luv = lca(ou, ov)
    u, v = ou, ov
    
    distu = dist[u] - dist[luv]
    for i in range(distu.bit_length()):
        if (1<<i) & distu:
            data[i][u] = max(data[i][u], x)
            u = D[i][u]
    
    distv = dist[v] - dist[luv]
    for i in range(distv.bit_length()):
        if (1<<i) & distv:
            data[i][v] = max(data[i][v], x)
            v = D[i][v]

def query(u, v):
    res = inf
    if dist[u] > dist[v]:
        u, v = v, u
    
    ddif = dist[v] - dist[u]
    for i in range(ddif.bit_length()):
        if (1<<i)&ddif:
            res = min(res, Dmin[i][v])
            v = D[i][v]            
    if u != v:
        for cnt in range(dist[u].bit_length()-1, -1, -1):
            if D[cnt][u] != D[cnt][v]:
                res = min(res, Dmin[cnt][u], Dmin[cnt][v])
                u = D[cnt][u]
                v = D[cnt][v]                
        res = min(res, path[u], path[v])
    return res
    
N = int(readline())
Edge = [[] for _ in range(N)]
for num in range(N-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    Edge[a].append((b, num))
    Edge[b].append((a, num))

root = 0
P, L, Einv = parorder(Edge, root)
P[root] = None
D = [P[:]]
dep = N.bit_length()
for _ in range(dep):
    ret = [None]*N
    for i in range(N):
        k = D[-1][i]
        if k is not None:
            ret[i] = D[-1][k]
    D.append(ret)

dist = [0]*N
for l in L[1:]:
    dist[l] = 1+dist[P[l]]

mini = 0
data = [[mini]*N for _ in range(dep)]

Q = int(readline())
qu = []
for _ in range(Q):
    a, b, c = map(int, readline().split())
    update(a-1, b-1, c)
    qu.append((a-1, b-1, c))

path = [1]*N
for l in L[::-1]:
    ret = [mini]*dep
    ret[dep-1] = data[dep-1][l]
    for idx in range(dep-2, -1, -1):
        ret[idx] = max(ret[idx+1], data[idx][l])
    
    path[l] = ret[0]
    for i in range(dep-1):
        if D[i][l] is None:
            break
        data[i][D[i][l]] = max(data[i][D[i][l]], ret[i+1])

inf = 10**6

for i in range(N):
    if path[i] == mini:
        path[i] = inf

Dmin = [path[:]]
for d in range(dep):
    res = [inf]*N
    for u in range(N):
        if D[d][u] is not None:
            res[u] = min(Dmin[-1][u], Dmin[-1][D[d][u]])
    Dmin.append(res)
for a, b, c in qu:
    if c != query(a, b):
        print(-1)
        break
else:
    ans = [inf]*(N-1)
    for i in range(N):
        if i != root:
            ans[Einv[i]] = path[i]
    print(*ans)