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:
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase
# Ref https://github.com/cheran-senthil/PyRival/tree/master/pyrival
# sys.modules["hashlib"] = sys.sha512 = sys
# import random

def dfsPre(par,graph,tin,tout):
    n = len(graph)
    visited, finished = [False] * n, [False] * n
    
    stack = [1]

    # print(tin,tout)
    t = 0
    while stack:
        start = stack[-1]
        if not visited[start]:
            visited[start]=True
            t+=1
            tin[start] = t 
            for child in graph[start]:
                if not visited[child]:
                    stack.append(child)
                    par[child] = start

        else:
            stack.pop()
            t+=1
            tout[start] = t 

def parent(tin,tout,u,v):
    return tin[u]<=tin[v] and tout[v]<=tout[u]

def dfs(par,tin,tout,adj,u,v,c):
    while(not parent(tin,tout,u,v)):
        adj[u][par[u]]=max(adj[u][par[u]],c)
        u=par[u]

def dfs1(par,tin,tout,adj,u,v):
    ans = 10000000
    while(not parent(tin,tout,u,v)):
        ans=min(ans,adj[u][par[u]])
        u=par[u]
    return ans


# def rnd(v):
#     random.shuffle(v)
#     return v

def main():
    n = int(input())
    edges = [ [int(x) for x in input().split()] for i in range(n-1) ]
    m = int(input())
    qur = [ [int(x) for x in input().split()] for i in range(m) ]
    graph = [ [] for i in range(n+1) ]
    adj = [ [1 for j in range(n+1)] for i in range(n+1) ]
    par = [-1]*(n+1)
    tin = [0]*(n+1)
    tout = [0]*(n+1)
    
    for x in edges:
        graph[x[0]].append(x[1])
        graph[x[1]].append(x[0])
    
    dfsPre(par,graph,tin,tout)
    
    chk = {}
    for x in qur:
        u,v,c=x[0],x[1],x[2]
        if(u>v):
            u,v=v,u
        fl = False
        try:
            j=chk[u*(n+1)+v]
            if j !=c :
                print(-1)
                fl = True
        except:
            chk[u*(n+1)+v] = c
            dfs(par,tin,tout,adj,u,v,c)
            dfs(par,tin,tout,adj,v,u,c)
        
        if(fl):
            exit(0)
    
    for i in range(1,n+1):
        for j in range(i+1,n+1):
            adj[i][j]=adj[j][i]=max(adj[i][j],adj[j][i])

    for x,y in chk.items():
        u,v=x//(n+1),x%(n+1)
        if(min(dfs1(par,tin,tout,adj,v,u),dfs1(par,tin,tout,adj,u,v))!=y):
            print(-1)
            exit(0)
    for x in edges:
        print(adj[x[0]][x[1]],end=" ")

# region fastio

BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()