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:
from collections import defaultdict

# n - 1 is number of edges
# p is number of passengers
# O(n + plog(p) + p*n) solution
# Find shortest path and write min (high to low) on any still unset edges.
# Shortest path via dfs/bfs TLEs.
# Root the tree so you can find short path just by walking up to LCA.
# Had to micro-optimize a lot before it was fast...


def solve(edges, passengers):
    N = len(edges) + 1
    g = defaultdict(lambda: defaultdict(int))
    for edgeId, e in enumerate(edges):
        g[e[0]][e[1]] = edgeId
        g[e[1]][e[0]] = edgeId

    # Do a DFS to (arbitrarily) root the tree and record depths
    parent = [None] * N
    parentEdge = [None] * N
    depth = [None] * N
    parent[0] = float("inf")
    parentEdge[0] = float("inf")
    depth[0] = 0
    stack = [0]
    while stack:
        node = stack.pop()
        for k, edgeId in g[node].items():
            if parent[k] is None:
                parent[k] = node
                parentEdge[k] = edgeId
                depth[k] = depth[node] + 1
                stack.append(k)

    def getEdges(source, dest):
        # Find shortest path by walking both nodes up till their LCA
        # Returns the edge ids in arbitrary order!
        node1 = source
        node2 = dest
        # Start them at the same depth first
        d1 = depth[node1]
        d2 = depth[node2]
        while d1 > d2:
            yield parentEdge[node1]
            node1 = parent[node1]
            d1 -= 1
        while d1 < d2:
            yield parentEdge[node2]
            node2 = parent[node2]
            d2 -= 1
        assert d1 == d2
        # Walk up both paths until find lca
        while node1 != node2:
            yield parentEdge[node1]
            node1 = parent[node1]
            yield parentEdge[node2]
            node2 = parent[node2]
        assert node1 == node2

    # Sort by score, high to low
    passengers.sort(key=lambda t: t[3], reverse=True)

    # For each passenger, set any unset edges in their path to their min score
    edgeToScore = [None] * (N - 1)
    for p, a, b, score in passengers:
        numEdges = 0
        for edgeId in getEdges(a, b):
            if edgeToScore[edgeId] is None:
                numEdges += 1
                edgeToScore[edgeId] = score
            else:
                # Since sorted any existing scores must higher or equal
                # Can't overwrite lower because will lower the previous's min score
                score2 = edgeToScore[edgeId]
                assert score2 >= score
                if score2 == score:
                    numEdges += 1
        # Need to set at least one edge
        if numEdges == 0:
            return -1

    return " ".join(str(score) if score is not None else "1" for score in edgeToScore)


if False:
    import sys

    N = 5000
    edges = list(zip(range(N - 1), range(1, N)))
    passengers = [(p, 0, p, N - p) for p in range(1, N)]
    print(solve(edges, passengers))
    sys.exit()

if __name__ == "__main__":
    N = int(input())
    edges = []
    for edgeId in range(N - 1):
        x, y = map(int, input().split())
        edges.append((x - 1, y - 1))
    P = int(input())
    passengers = []
    for p in range(P):
        a, b, score = map(int, input().split())
        passengers.append((p, a - 1, b - 1, score))
    ans = solve(edges, passengers)
    print(ans)