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 JAVA):

Solution:
/*
    Those who cannot remember the past are condemned to repeat it.
                                            - Dynamic Programming
    
    I never lose, I either win or I learn.
                - Competitive Programming

*/

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class TaskF {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        PrintWriter pw = new PrintWriter(System.out);

        int n = Integer.parseInt(br.readLine());

        Tree tree = new Tree(n);

        for(int i=0 ; i<n-1 ; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            tree.addEdge(u, v, i);
        }

        int m = Integer.parseInt(br.readLine());

        Journey[] journeys = new Journey[m];

        for(int i=0 ; i<m ; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int beauty = Integer.parseInt(st.nextToken());
            journeys[i] = new Journey(u, v, beauty);
        }

        Arrays.sort(journeys, (o1, o2) -> o2.beauty-o1.beauty);

        int[] f = new int[n-1];

        boolean possible = true;

        for(int i=0 ; i<m ; i++) {
            Stack<Integer> path_nodes = new Stack<>();
            Arrays.fill(tree.vis, false);
            tree.dfs(path_nodes, journeys[i].u, journeys[i].v);

            Iterator<Integer> it = path_nodes.iterator();
            int start = it.next();
            int next = 0;
            ArrayList<Integer> path_edges = new ArrayList<>();
            while(it.hasNext()) {
                next = it.next();
                path_edges.add(tree.edge_index[start][next]);
                start = next;
            }

            int min_beauty = Integer.MAX_VALUE;
            for(int ind: path_edges) {
                if(f[ind] == 0) f[ind] = journeys[i].beauty;
                min_beauty = Math.min(min_beauty, f[ind]);
            }

            if(min_beauty != journeys[i].beauty) {
                possible = false;
                break;
            }
        }

        if(possible) {
            for(int i=0 ; i<n-1 ; i++) {
                if(f[i] == 0) f[i] = 1;
                pw.print(f[i] + " ");
            }
            pw.println();
        }
        else {
            pw.println(-1);
        }



        pw.flush();
        pw.close();
    }
}

class Tree {
    int n;
    ArrayList<Integer>[] adj;
    int[][] edge_index;
    boolean[] vis;

    Tree(int v) {
        n = v;
        adj = new ArrayList[n+1];
        for(int i=0 ; i<=n ; i++) adj[i] = new ArrayList<>();
        edge_index = new int[n+1][n+1];
        vis = new boolean[n+1];
    }

    void addEdge(int u, int v, int i) {
        adj[u].add(v);
        adj[v].add(u);
        edge_index[u][v] = i;
        edge_index[v][u] = i;
    }

    boolean dfs(Stack<Integer> path, int start, int end) {
        vis[start] = true;
        path.add(start);
        if(start == end) return true;
        for(int x: adj[start]) {
            if(!vis[x]) {
                boolean done = dfs(path, x, end);
                if(done) return true;
            }
        }
        path.pop();
        return false;
    }


}

class Journey {
    int u;
    int v;
    int beauty;
    Journey(int a, int b, int c) {
        u = a;
        v = b;
        beauty = c;
    }
}