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:
import java.awt.*;
import java.io.*;
import java.util.*;

public class Main {
    static ArrayList<Integer> adj[];
    static int map[][];
    static boolean checker;
    static int par[][];
    public static void main(String[] args) throws Exception {
        FastReader sc = new FastReader();
        int n = sc.nextInt();
        adj = new ArrayList[n];
        ArrayList<Point> edges = new ArrayList<>();
        map = new int[n][n];
        par=new int [n][n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int i = 0; i < n - 1; i++) {
            int a = sc.nextInt() - 1, b = sc.nextInt() - 1;
            adj[a].add(b);
            adj[b].add(a);
            edges.add(new Point(a, b));
        }
        int m = sc.nextInt();
        Point p[] = new Point[m];
        int values[] = new int[m];
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt() - 1, b = sc.nextInt() - 1, val = sc.nextInt();
            p[i] = new Point(a, b);
            values[i] = val;
            par[a][a]=a;
            dfs(a, b, val,a);
        }
        for (int i = 0; i < m; i++) {
//            checker = false;
//            dfss(p[i].x, p[i].y, values[i], p[i].x);
//            if (!checker) {
//                System.out.println(-1);
//                System.exit(0);
//            }
            int root=p[i].x;
            int src=p[i].x,dest=p[i].y;
            int u=par[root][dest],v=dest;
            boolean f=false;
            while (u!=v){
                if (map[u][v]<values[i]){
                    System.out.println(-1);
                    System.exit(0);
                }
                if (map[u][v]==values[i])f=true;
                v=u;
                u=par[root][v];
            }
            if (!f){
                System.out.println(-1);
                System.exit(0);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n - 1; i++) {
            Point xx = edges.get(i);
            int x = map[xx.x][xx.y];
            if (x == 0) x = 1000000;
            sb.append(x + " ");
        }
        System.out.println(sb);

    }

//    static boolean dfss(int src, int dest, int val, int par) {
//        if (src == dest) {
//            return true;
//        }
//        for (int u : adj[src]) {
//            if (u != par) {
//                boolean x = dfss(u, dest, val, src);
//                if (x) {
//                    int y = map[src][u];
//                    if (y < val) {
//                        System.out.println(-1);
//                        System.exit(0);
//                    }
//                    if (y == val) checker = true;
//                    return true;
//                }
//            }
//        }
//        return false;
//    }

    static boolean dfs(int src, int dest, int val,int root) {
        if (dest == src) {
            return true;
        }
        for (int u : adj[src]) {
            if (u != par[root][src]) {
                par[root][u]=src;
                boolean b = dfs(u, dest, val,root);
                if (b) {
                    if (map[src][u] != 0) {
                        int x = Math.max(map[src][u], val);
                        map[src][u] = x;
                        map[u][src] = x;
                    } else {
                        map[src][u] = val;
                        map[u][src] = val;
                    }
                    return b;
                }
            }
        }
        return false;
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}