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.util.*;
import java.io.*;
import java.text.*;

public class F1296 {

	static ArrayList<Pair>[] adj;
	static int[] tm;
	static int[][] tm2, tm22, adjList, adjList2;
	static int n;

	public static void process(int a, int b, int w) {
		int[] p;
		int[] pp;
		p = new int[adjList.length];
		pp = new int[adjList.length];
		if (tm2[a] == null) {
			Queue<Integer> q = new LinkedList<Integer>();
//			int idx = 0;
			q.add(a);
			p[a] = -1;
			pp[a] = -1;
			while (!q.isEmpty()) {
				int cur = q.poll();
				for (int i = 0; i < adjList[cur].length; i++) {
					int x = adjList[cur][i];
					if (x != p[cur]) {
						p[x] = cur;
						pp[x] = adjList2[cur][i];
						q.add(x);
					}
				}
			}
			tm2[a] = p;
			tm22[a] = pp;
		} else {
			p = tm2[a];
			pp = tm22[a];
		}

		int g = b;
		while (g != a) {
			tm[pp[g]] = w;
			g = p[g];
		}
	}

	public static boolean check(int a, int b, int w) {
		int[] p = tm2[a];
		int[] pp = tm22[a];
		int g = b;
		int min = (int) 1e9;
		while (g != a) {
			min = Math.min(min, Math.max(tm[pp[g]], 1));
			g = p[g];
		}
		return min == w;
	}

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		n = sc.nextInt();
		adj = new ArrayList[n];
		adjList = new int[n][];
		adjList2 = new int[n][];
		tm2 = new int[n][];
		tm22 = new int[n][];
		for (int i = 0; i < n; i++)
			adj[i] = new ArrayList<Pair>();
		int[] u = new int[n - 1];
		int[] v = new int[n - 1];
		for (int i = 0; i < n - 1; i++) {
			u[i] = sc.nextInt() - 1;
			v[i] = sc.nextInt() - 1;
			adj[u[i]].add(new Pair(v[i], i));
			adj[v[i]].add(new Pair(u[i], i));
		}
		for (int i = 0; i < n; i++) {
			adjList[i] = new int[adj[i].size()];
			adjList2[i] = new int[adjList[i].length];
			for (int j = 0; j < adjList[i].length; j++) {
				adjList[i][j] = adj[i].get(j).x;
				adjList2[i][j] = adj[i].get(j).y;
			}
		}
		tm = new int[n];
		int m = sc.nextInt();
		int[] a = new int[m], b = new int[m], w = new int[m];
		for (int i = 0; i < w.length; i++) {
			a[i] = sc.nextInt() - 1;
			b[i] = sc.nextInt() - 1;
			w[i] = sc.nextInt();
		}
		Integer[] q = new Integer[m];
		for (int i = 0; i < q.length; i++) {
			q[i] = i;
		}

		Arrays.sort(q, (aa, bb) -> w[aa] - w[bb]);
		for (int i = 0; i < m; i++) {
			process(a[q[i]], b[q[i]], w[q[i]]);
		}
		boolean valid = true;
		for (int i = 0; i < q.length; i++) {
			valid &= check(a[i], b[i], w[i]);
		}
		if (valid) {
			for (int i = 0; i < n - 1; i++) {
				pw.print(Math.max(tm[i], 1));
				pw.print(" ");
			}
			pw.println();
		} else {
			pw.println(-1);
		}
//		pw.println(tm);
		pw.close();

	}

	static class Pair {
		int x, y;

		public Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}

		public String toString() {
			return x + " " + y;
		}

	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(FileReader r) {
			br = new BufferedReader(r);
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}
}