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.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;
import java.util.function.*;


public class F {

    private static final FastReader in = new FastReader();
    private static final FastWriter out = new FastWriter();

    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(IntPair.of(u, v));
        }
        lca.build();

        var m = in.nextInt();
        var queries = new ArrayList<IntTriple>();
        for (var i = 0; i < m; i++) {
            var q = IntTriple.of(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.parent(u) == v) {
                    var t = u;
                    u = v;
                    v = t;
                }

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

        out.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.parent(u);
        }

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

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

        return valid;
    }

}


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 double[] nextDoubleArray(int length) {
        var a = new double[length];
        for (var i = 0; i < length; i++) {
            a[i] = nextDouble();
        }
        return a;
    }

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

    public int[] nextIntArray(int length) {
        var a = new int[length];
        for (var i = 0; i < length; i++) {
            a[i] = nextInt();
        }
        return a;
    }

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

    public long[] nextLongArray(int length) {
        var a = new long[length];
        for (var i = 0; i < length; i++) {
            a[i] = nextLong();
        }
        return a;
    }

}


class FastWriter extends PrintWriter {

    public FastWriter() {
        super(System.out);
    }

    public void println(double[] a) {
        for (var i = 0; i < a.length; i++) {
            print(a[i]);
            print(i + 1 < a.length ? ' ' : '\n');
        }
    }

    public void println(int[] a) {
        for (var i = 0; i < a.length; i++) {
            print(a[i]);
            print(i + 1 < a.length ? ' ' : '\n');
        }
    }

    public void println(long[] a) {
        for (var i = 0; i < a.length; i++) {
            print(a[i]);
            print(i + 1 < a.length ? ' ' : '\n');
        }
    }

    public <T> void println(T[] a) {
        for (var i = 0; i < a.length; i++) {
            print(a[i]);
            print(i + 1 < a.length ? ' ' : '\n');
        }
    }

    public 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);
    }

}


class IntPair extends Pair<Integer, Integer> {

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

    public static IntPair of(int a, int b) {
        return new IntPair(a, b);
    }

}


class IntTriple extends Triple<Integer, Integer, Integer> {

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

    public static IntTriple of(int a, int b, int c) {
        return new IntTriple(a, b, c);
    }

}



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 parent(int u) {
        return nodes.get(u).parent.label;
    }

    public int distance(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 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 String toString() {
            return "LCA.Edge(neighbor=" + this.neighbor.label + ", weight=" + this.weight + ")";
        }

    }

}


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));
    }

}

class Triple<T, U, V> {

    public T a;
    public U b;
    public V c;

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

    public static <T, U, V> Triple<T, U, V> of(T a, U b, V c) {
        return new Triple<>(a, b, c);
    }

    public T getA() {
        return a;
    }

    public U getB() {
        return b;
    }

    public V getC() {
        return c;
    }

    @Override
    public String toString() {
        return "Triple(a=" + this.getA() + ", b=" + this.getB() + ", c=" + this.getC() + ")";
    }

}

class Pair<T, U> {

    public T a;
    public U b;

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

    public static <T, U> Pair<T, U> of(T a, U b) {
        return new Pair<>(a, b);
    }

    public T getA() {
        return a;
    }

    public U getB() {
        return b;
    }

    @Override
    public String toString() {
        return "Pair(a=" + this.getA() + ", b=" + this.getB() + ")";
    }

}