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.util.*;

public class ProblemF {

    public static InputStream inputStream = System.in;

    public static OutputStream outputStream = System.out;

    public static void main(String[] args) {
        MyScanner scanner = new MyScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);

        int n = scanner.nextInt();
        Graph graph = new Graph(n);
        List<Pair<Integer, Integer>> edges = new ArrayList<>();
        for (int i = 0; i < n - 1; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            graph.addEdge(x, y);
            edges.add(new Pair<>(x, y));
        }

        int m = scanner.nextInt();
        List<Pair<Pair<Integer, Integer>, Integer>> list = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int w = scanner.nextInt();
            list.add(new Pair<>(new Pair<>(x, y), w));
        }

        Collections.sort(list, (a, b) -> Integer.compare(b.second, a.second));

        boolean can = true;
        for (Pair<Pair<Integer, Integer>, Integer> pair : list) {
            can = can & graph.fillF(pair.first.first, pair.first.second, pair.second);
        }

        if (!can) {
            out.print(-1);
        } else {
            for (Pair<Integer, Integer> edge : edges) {
                int a = Math.min(edge.first, edge.second);
                int b = Math.max(edge.first, edge.second);
                int x = graph.f[a][b];
                if (x == 0) {
                    out.print(1_000_000 + " ");
                } else {
                    out.print(x + " ");
                }
            }
        }





        out.flush();
    }

    private static class Graph {

        private Map<Integer, Node> nodes = new HashMap<>();

        private int[][] f;

        private Graph(int n) {
            for (int i = 1; i <= n; i++) {
                nodes.put(i, new Node(i));
            }
            f = new int[n + 1][n + 1];
        }

        private void addEdge(int x, int y) {
            nodes.get(x).adjacents.add(nodes.get(y));
            nodes.get(y).adjacents.add(nodes.get(x));
        }

        private boolean fillF(int x, int y, int w) {
            for (Node node : nodes.values()) {
                node.clean();
            }

            LinkedList<Node> toVisit = new LinkedList<>();
            toVisit.add(nodes.get(x));
            while (!toVisit.isEmpty()) {
                Node node = toVisit.poll();
                node.visited = true;
                if (node.label == y) {
                    break;
                }
                for (Node adjacent : node.adjacents) {
                    if (!adjacent.visited) {
                        adjacent.from = node;
                        adjacent.visited = true;
                        toVisit.add(adjacent);
                    }
                }
            }

            Node dest = nodes.get(y);
            boolean found = false;
            while (dest.from != null) {
                int a = Math.min(dest.label, dest.from.label);
                int b = Math.max(dest.label, dest.from.label);
                if (f[a][b] == 0 || f[a][b] == w) {
                    f[a][b] = w;
                    found = true;
                }
                dest = dest.from;
            }

            return found;
        }
    }

    private static class Node {

        private int label;

        private List<Node> adjacents = new ArrayList<>();

        private boolean visited;

        private Node from;

        private Node(int label) {
            this.label = label;
        }

        private void clean() {
            visited = false;
            from = null;
        }
    }

    private static class MyScanner {
        private BufferedReader bufferedReader;
        private StringTokenizer stringTokenizer;

        private MyScanner(InputStream inputStream) {
            bufferedReader = new BufferedReader(new InputStreamReader(inputStream));
        }

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

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

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

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

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

    private static class Pair<F, S> {

        private F first;

        private S second;

        public Pair() {}

        public Pair(F first, S second) {
            this.first = first;
            this.second = second;
        }
    }
}