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.io.*;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.*;

/*
Прокрастинирую
*/

public class Main {

    static FastReader in;
    static PrintWriter out;
    static Random rand = new Random();
    static final int INF = (int) (1e9 + 10);
    static final int MOD = (int) (1e9 + 7);
    static final int N = (int) (1e6);
    static final int LOGN = 20;
    static int n, m;
    static ArrayList<Integer>[] g;
    static int[][] gg;
    static Edge[] edges;
    static Q[] qs;
    static int[] p;

    static class Edge {
        int v, u;

        Edge(int v, int u) {
            this.v = v;
            this.u = u;
        }
    }

    static class Q {
        int v, u, w;

        Q(int v, int u, int w) {
            this.v = v;
            this.u = u;
            this.w = w;
        }
    }

    static void dfs(int v, int from) {
        p[v] = from;
        for (int u : g[v]) {
            if (u != from) {
                dfs(u, v);
            }
        }
    }

    static void solve() {
        n = in.nextInt();

        g = new ArrayList[n];
        Arrays.setAll(g, gi -> new ArrayList<>());
        gg = new int[n][n];
        edges = new Edge[n - 1];
        for (int i = 0; i < n - 1; i++) {
            int v = in.nextInt() - 1;
            int u = in.nextInt() - 1;
            g[v].add(u);
            g[u].add(v);
            edges[i] = new Edge(v, u);
        }

        m = in.nextInt();
        qs = new Q[m];
        for (int i = 0; i < m; i++) {
            int v = in.nextInt() - 1;
            int u = in.nextInt() - 1;
            int w = in.nextInt();
            qs[i] = new Q(v, u, w);
        }
        Arrays.sort(qs, (o1, o2) -> Integer.compare(o2.w, o1.w));

        p = new int[n];
        for (Q q : qs) {
            int v = q.v;
            int u = q.u;
            int w = q.w;
            Arrays.fill(p, -1);
            dfs(v, v);
            ArrayList<Integer> path = new ArrayList<>();
            path.add(u);
            while (u != v) {
                u = p[u];
                path.add(u);
            }
            Collections.reverse(path);

            int min = INF;
            for (int j = 1; j < path.size(); j++) {
                v = path.get(j - 1);
                u = path.get(j);
                if (gg[v][u] == 0) {
                    gg[v][u] = gg[u][v] = w;
                }
                min = Math.min(min, gg[v][u]);
            }
            if (min != w) {
                out.println(-1);
                return;
            }
        }

        for (Edge e : edges) {
            int v = e.v;
            int u = e.u;
            if (gg[v][u] == 0) {
                out.print(1 + " ");
            } else {
                out.print(gg[v][u] + " ");
            }
        }
        out.println();
    }

    public static void main(String[] args) throws FileNotFoundException {
        in = new FastReader(System.in);
//        in = new FastReader(new FileInputStream("sometext.txt"));
        out = new PrintWriter(System.out);
//        out = new PrintWriter(new FileOutputStream("output.txt"));


        int q = 1;

        while (q-- > 0) {
            solve();
        }

        out.close();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        FastReader(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

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

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

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

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                st = new StringTokenizer(nextLine());
            }
            return st.nextToken();
        }

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