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 CF1296F extends PrintWriter {
	CF1296F() { super(System.out, true); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF1296F o = new CF1296F(); o.main(); o.flush();
	}

	int[] oo, oh; int __ = 1;
	int link(int o, int h) {
		oo[__] = o; oh[__] = h;
		return __++;
	}
	int[] ij;
	int[] ae, dd, ff, gg_;
	void init(int n) {
		int m = n - 1;
		oo = new int[1 + m * 2]; oh = new int[1 + m * 2];
		ij = new int[m];
		ae = new int[n]; dd = new int[n]; ff = new int[n];
		gg_ = new int[n]; Arrays.fill(gg_, 1);
	}
	void dfs(int h_, int i, int d) {
		ff[i] = h_;
		dd[i] = d;
		for (int o = ae[i]; o != 0; o = oo[o]) {
			int h = oh[o], j = i ^ ij[h];
			if (h != h_)
				dfs(h, j, d + 1);
		}
	}
	void main() {
		int n = sc.nextInt();
		init(n);
		for (int h = 0; h < n - 1; h++) {
			int i = sc.nextInt() - 1;
			int j = sc.nextInt() - 1;
			ij[h] = i ^ j;
			ae[i] = link(ae[i], h);
			ae[j] = link(ae[j], h);
		}
		dfs(-1, 0, 0);
		int q = sc.nextInt();
		int[] ii = new int[q];
		int[] jj = new int[q];
		int[] gg = new int[q];
		for (int h = 0; h < q; h++) {
			int i = sc.nextInt() - 1;
			int j = sc.nextInt() - 1;
			int g = sc.nextInt();
			if (dd[i] < dd[j]) {
				int tmp = i; i = j; j = tmp;
			}
			ii[h] = i; jj[h] = j; gg[h] = g;
			while (dd[i] > dd[j]) {
				gg_[i] = Math.max(gg_[i], g);
				i ^= ij[ff[i]];
			}
			while (i != j) {
				gg_[i] = Math.max(gg_[i], g);
				gg_[j] = Math.max(gg_[j], g);
				i ^= ij[ff[i]];
				j ^= ij[ff[j]];
			}
		}
out:
		for (int h = 0; h < q; h++) {
			int i = ii[h], j = jj[h], g = gg[h];
			while (dd[i] > dd[j]) {
				if (gg_[i] == g)
					continue out;
				i ^= ij[ff[i]];
			}
			while (i != j) {
				if (gg_[i] == g || gg_[j] == g)
					continue out;
				i ^= ij[ff[i]];
				j ^= ij[ff[j]];
			}
			println(-1);
			return;
		}
		int[] ans = new int[n - 1];
		for (int i = 1; i < n; i++)
			ans[ff[i]] = gg_[i];
		for (int h = 0; h < n - 1; h++)
			print(ans[h] + " ");
		println();
	}
}