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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.*;
import java.util.*;
import java.util.function.*;

public class F {

    private static final FastReader in = new FastReader();
    private static final PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        new F().run();
    }

    private void run() {
        var t = 1;
        while (t-- > 0) {
            solve();
        }

        out.flush();
    }

    private LCA lca;
    private int[] w;

    private void solve() {
        var n = in.nextInt();
        lca = new LCA(n);

        var edges = new ArrayList<IntPair>(n - 1);
        for (var i = 1; i < n; i++) {
            var u = in.nextInt() - 1;
            var v = in.nextInt() - 1;
            lca.addBidirectedEdges(u, v);
            edges.add(new IntPair(u, v));
        }
        lca.build();

        var m = in.nextInt();
        var queries = new ArrayList<IntTriple>();
        for (var i = 0; i < m; i++) {
            var q = new IntTriple(in.nextInt() - 1, in.nextInt() - 1, in.nextInt());
            queries.add(q);
        }

        queries.sort(Comparator.comparing(IntTriple::getC).reversed());

        w = new int[n];
        for (var q : queries) {
            if (!mark(q)) {
                out.println(-1);
                return ;
            }
        }

        var f = edges.stream()
            .mapToInt(e -> {
                var u = e.a;
                var v = e.b;
                if (lca.getParent(u) == v) {
                    var t = u;
                    u = v;
                    v = t;
                }

                return w[v] > 0 ? w[v] : 1;
            })
            .toArray();

        println(f);
    }

    boolean mark(IntTriple q) {
        boolean valid = false;
        int ancestor = lca.query(q.a, q.b);

        int u = q.a;
        while (u != ancestor) {
            if (w[u] == 0) {
                w[u] = q.c;
            }

            valid |= w[u] == q.c;
            u = lca.getParent(u);
        }

        int v = q.b;
        while (v != ancestor) {
            if (w[v] == 0) {
                w[v] = q.c;
            }

            valid |= w[v] == q.c;
            v = lca.getParent(v);
        }

        return valid;
    }

    @SuppressWarnings("unused")
    private static void println(int[] a) {
        for (var i = 0; i < a.length; i++) {
            out.print(a[i]);
            out.print(i + 1 < a.length ? ' ' : '\n');
        }
    }

    @SuppressWarnings("unused")
    private static void debug(String name, Object o) {
        String value = Arrays.deepToString(new Object[] { o });
        value = value.substring(1, value.length() - 1);
        System.err.println(name + " => " + value);
    }

    @SuppressWarnings("unused")
    private static int binarySearch(int left, int right, Predicate<Integer> leftShouldAdvance) {
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (leftShouldAdvance.test(mid)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }

    @SuppressWarnings("unused")
    private static class Pair<T, U> {

        T a;
        U b;

        Pair(T a, U b) {
            this.a = a;
            this.b = b;
        }

        T getA() {
            return a;
        }

        U getB() {
            return b;
        }

    }

    @SuppressWarnings("unused")
    private static class IntPair extends Pair<Integer, Integer> {

        IntPair(Integer a, Integer b) {
            super(a, b);
        }

    }

    @SuppressWarnings("unused")
    private static class Triple<T, U, V> {

        T a;
        U b;
        V c;

        Triple(T a, U b, V c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }

        T getA() {
            return a;
        }

        U getB() {
            return b;
        }

        V getC() {
            return c;
        }

    }

    @SuppressWarnings("unused")
    private static class IntTriple extends Triple<Integer, Integer, Integer> {

        IntTriple(Integer a, Integer b, Integer c) {
            super(a, b, c);
        }

    }

    @SuppressWarnings("unused")
    private static class FastReader {

        private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        private static StringTokenizer in;

        public String next() {
            while (in == null || !in.hasMoreTokens()) {
                try {
                    in = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    return null;
                }
            }
            return in.nextToken();
        }

        public BigDecimal nextBigDecimal() {
            return new BigDecimal(next());
        }

        public BigInteger nextBigInteger() {
            return new BigInteger(next());
        }

        public boolean nextBoolean() {
            return Boolean.valueOf(next());
        }

        public byte nextByte() {
            return Byte.valueOf(next());
        }

        public double nextDouble() {
            return Double.valueOf(next());
        }

        public int nextInt() {
            return Integer.valueOf(next());
        }

        public long nextLong() {
            return Long.valueOf(next());
        }

    }

    static class LCA {

        private final List<Node> nodes;
        private final List<Node> eulerTour;
        private RMQ<Node> rmq;

        public LCA(int n) {
            this.nodes = new ArrayList<>(n);
            this.eulerTour = new ArrayList<>(n * 2 - 1);

            for (var i = 0; i < n; i++) {
                nodes.add(new Node(i));
            }
        }

        public void addEdge(int u, int v) {
            addEdge(u, v, 1);
        }

        public void addEdge(int u, int v, int weight) {
            nodes.get(u).addNeighbor(nodes.get(v), weight);
        }

        public void addBidirectedEdges(int u, int v) {
            addBidirectedEdges(u, v, 1);
        }

        public void addBidirectedEdges(int u, int v, int weight) {
            addEdge(u, v, weight);
            addEdge(v, u, weight);
        }

        public void build() {
            build(0);
        }

        public void build(int root) {
            dfs(nodes.get(root), new Node(-1), 0, 0);
            rmq = new RMQ<>(eulerTour);
        }

        public int query(int x, int y) {
            var l = nodes.get(x).firstSeenInEulerTour;
            var r = nodes.get(y).firstSeenInEulerTour;
            if (l > r) {
                var t = l;
                l = r;
                r = t;
            }

            return rmq.query(l, r + 1).label;
        }

        public int getParent(int u) {
            return nodes.get(u).parent.label;
        }

        public int getDistance(int x, int y) {
            return nodes.get(x).distance + nodes.get(y).distance - nodes.get(query(x, y)).distance * 2;
        }

        private int dfs(Node u, Node parent, int preOrderIndex, int distance) {
            u.parent = parent;
            u.distance = distance;
            u.preOrderIndex = preOrderIndex;
            u.firstSeenInEulerTour = eulerTour.size();
            eulerTour.add(u);

            var subTreeSize = 1;
            for (var e : u.neighbors) {
                var v = e.neighbor;
                if (v.label != parent.label) {
                    subTreeSize += dfs(v, u, preOrderIndex + subTreeSize, u.distance + e.weight);
                    eulerTour.add(u);
                }
            }

            return subTreeSize;
        }

        private static class Node implements Comparable<Node> {

            final int label;
            final List<Edge> neighbors = new ArrayList<>();

            Node parent;
            int distance;
            int preOrderIndex;
            int firstSeenInEulerTour;

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

            public void addNeighbor(Node neighbor, int weight) {
                neighbors.add(new Edge(neighbor, weight));
            }

            @Override
            public int compareTo(Node o) {
                return Integer.compare(this.preOrderIndex, o.preOrderIndex);
            }

            @Override
            public java.lang.String toString() {
                return "LCA.Node("
                    + "label=" + this.label + ", "
                    + "neighbors=" + this.neighbors + ", "
                    + "parent=" + this.parent + ", "
                    + "distance=" + this.distance + ", "
                    + "preOrderIndex=" + this.preOrderIndex + ", "
                    + "firstSeenInEulerTour=" + this.firstSeenInEulerTour
                    + ")";
            }

        }

        private static class Edge {

            Node neighbor;
            int weight;

            Edge(Node neighbor, int weight) {
                this.neighbor = neighbor;
                this.weight = weight;
            }

            @Override
            public java.lang.String toString() {
                return "LCA.Edge(neighbor=" + this.neighbor.label + ", weight=" + this.weight + ")";
            }

        }

        private static class RMQ<T extends Comparable<T>> {

            private final int n;
            private final List<T> values;
            private final Comparator<T> comparator;
            private final int[][] ranges;

            public RMQ(List<T> values) {
                this(values, Comparator.naturalOrder());
            }

            public RMQ(List<T> values, Comparator<T> comparator) {
                this.values = values;
                this.comparator = comparator;
                this.n = values.size();
                this.ranges = new int[leftMostOneBit(n) + 1][];

                build();
            }

            private int leftMostOneBit(int x) {
                return Integer.SIZE - 1 - Integer.numberOfLeadingZeros(x);
            }

            private void build() {
                ranges[0] = new int[n];
                for (var i = 0; i < n; i++) {
                    ranges[0][i] = i;
                }

                for (var i = 1; 1 << i <= n; i++) {
                    ranges[i] = new int[n - (1 << i) + 1];
                    for (var j = 0; j + (1 << i) <= n; j++) {
                        ranges[i][j] = betterIndex(ranges[i - 1][j], ranges[i - 1][j + (1 << (i - 1))]);
                    }
                }
            }

            private int betterIndex(int l, int r) {
                return comparator.compare(values.get(l), values.get(r)) < 0 ? l : r;
            }

            public int queryIndex(int l, int r) {
                var exponent = leftMostOneBit(r - l);
                return betterIndex(ranges[exponent][l], ranges[exponent][r - (1 << exponent)]);
            }

            public T query(int l, int r) {
                return values.get(queryIndex(l, r));
            }

        }

    }
}