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:
/*
javac f.java && java f
*/

import java.io.*;
import java.util.*;
import java.lang.*;

public class f {
	public static void main(String[] args) { new f(); }
	FS in = new FS();
	PrintWriter out = new PrintWriter(System.out);

	int n, m;
	int[] a, b, s, ePtr;
	int[][] og, edge, eID;

	int[] q = new int[11313];
	int l = 0, r = 0;
	int u, v, w, mn, id;
	int node, par, ch;

	f() {
		n = in.nextInt();

		ePtr = new int[n];
		og = new int[n - 1][];
		edge = new int[n][];
		eID = new int[n][];
		for (int i = 0; i < n - 1; i++) {
			u = in.nextInt() - 1;
			v = in.nextInt() - 1;
			og[i] = new int[]{u, v, i};
			ePtr[u]++;
			ePtr[v]++;
		}
		for (int i = 0; i < n; i++) {
			edge[i] = new int[ePtr[i]];
			eID[i] = new int[ePtr[i]];
			ePtr[i] = 0;
		}
		for (int i = 0; i < n - 1; i++) {
			u = og[i][0];
			v = og[i][1];
			id = og[i][2];
			edge[u][ePtr[u]] = v;
			eID[u][ePtr[u]++] = id;
			edge[v][ePtr[v]] = u;
			eID[v][ePtr[v]++] = id;
		}
		
		m = in.nextInt();
		a = new int[m];
		b = new int[m];
		s = new int[m];
		for (int i = 0; i < m; i++) {
			a[i] = in.nextInt() - 1;
			b[i] = in.nextInt() - 1;
			s[i] = in.nextInt();
		}

		int[][] take = new int[n][n];
		for (int i = 0; i < n; i++) {
			l = 0; r = 0;
			q[r++] = i; q[r++] = i;

			int rte = 0;

			while (l != r) {
				if (rte++ > n) throw null;
				node = q[l++];
				par = q[l++];
				for (int j = 0; j < ePtr[node]; j++) {
					ch = edge[node][j];
					if (ch == par) continue;
					if (node == par) take[i][ch] = j;
					else take[i][ch] = take[i][node];
					q[r++] = ch; q[r++] = node;
				}
			}
		}

		boolean imp = false;
		int[] ans = new int[n - 1];
		Integer[] ord = new Integer[m];
		for (int i = 0; i < m; i++) ord[i] = i;
		Arrays.sort(ord, (x, y) -> s[y] - s[x]);
		for (int j = 0; j < m; j++) {
			int i = ord[j];
			u = a[i];
			v = b[i];
			mn = s[i];

			int rte = 0;

			boolean gt = true;
			while (u != v) {
				if (rte++ > n) throw null;
				w = edge[u][take[u][v]];
				id = eID[u][take[u][v]];
				gt &= (ans[id] > mn);
				ans[id] = max(ans[id], mn); 
				u = w;
			}
			imp |= gt;
			if (imp) break;
		}
		
		if (imp) out.println(-1);
		else {
			for (int i = 0; i < n - 1; i++) {
			 	id = og[i][2];
				if (ans[id] == 0) 
					ans[id] = 1;
				out.print(ans[id] + " ");
			}
			out.println();
		}
		out.close();
	}

	int abs(int x) { if (x < 0) return -x; return x; }
	long abs(long x) { if (x < 0) return -x; return x; }
	int min(int a, int b) { if (a < b) return a; return b; }	
	int max(int a, int b) { if (a > b) return a; return b; }	
	long min(long a, long b) { if (a < b) return a; return b; }	
	long max(long a, long b) { if (a > b) return a; return b; }	
	int gcd(int a, int b) { while (b > 0) { a = b^(a^(b = a)); b %= a; } return a; }
	long gcd(long a, long b) { while (b > 0) { a = b^(a^(b = a)); b %= a; } return a; }
	long lcm(int a, int b) { return ((long) a / gcd(a, b)) * b; }
	long lcm(long a, long b) { return (a / gcd(a, b)) * b; }

	void sort(int[] arr) {
		int sz = arr.length, j;
		Random r = new Random();
		for (int i = 0; i < sz; i++) {
			j = r.nextInt(i + 1);
			arr[i] = arr[j]^(arr[i]^(arr[j] = arr[i]));
		} Arrays.sort(arr);
	}

	class FS {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens()) {
				try { st = new StringTokenizer(br.readLine()); }
				catch (Exception e) {}
			} return st.nextToken();
		}
		int nextInt() { return Integer.parseInt(next()); }
		long nextLong() { return Long.parseLong(next()); }
		double nextDouble() { return Double.parseDouble(next()); }
	}
}