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  Main{
	static int log = 22;
	static int[] level, up[],max[];
	static LinkedList<Integer>[]adj;

	static void update(int u, int v,int val) {

		if (level[u] < level[v]) {
			update(v, u,val);
		
			return;
		}
		for (int i = log - 1; i >= 0; i--) {
			int u2 = up[u][i];
			if(u2==-1)continue;
			if (level[u2] >= level[v]) {
				max[u][i]=Math.max(max[u][i], val);
				u = u2;
			}
		}
		if (u == v)
			return;
		for (int i = log - 1; i >= 0; i--) {
			int u2 = up[u][i], v2 = up[v][i];
			if(u2==-1 || v2==-1)continue;
			if (u2 != v2) {
				max[u][i]=Math.max(max[u][i], val);
				max[v][i]=Math.max(max[v][i], val);
				u = u2;
				v = v2;
			}
		}
		max[u][0]=Math.max(max[u][0], val);
		max[v][0]=Math.max(max[v][0], val);
	}
	static int min(int u, int v) {
		if (level[u] < level[v]) {
			return min(v, u);
		}
		int min=1000000000;
		for (int i = log - 1; i >= 0; i--) {
			int u2 = up[u][i];
			if(u2==-1)continue;
			if (level[u2] >= level[v]) {
				min=Math.min(max[u][i], min);
				u = u2;
			}
		}
		if (u == v)
			return min;
		for (int i = log - 1; i >= 0; i--) {
			int u2 = up[u][i], v2 = up[v][i];
			if(u2==-1 || v2==-1)continue;
			if (u2 != v2) {
				min=Math.min(max[u][i], min);
				min=Math.min(max[v][i], min);
				u = u2;
				v = v2;
			}
		}
		min=Math.min(max[u][0], min);
		min=Math.min(max[v][0], min);
		return min;
	}
	static void propagate() {
		for(int l=log-1;l>0;l--) {
			for(int i=0;i<level.length;i++) {
					int par=up[i][l-1];
					max[i][l-1]=Math.max(max[i][l-1], max[i][l]);
					if(par==-1)continue;
					max[par][l-1]=Math.max(max[par][l-1], max[i][l]);
					
				
			}
		}
		
		for(int l=1;l<log;l++) {
			for(int i=0;i<level.length;i++) {
				int par=up[i][l-1];
				if(par==-1)continue;
				max[i][l]=Math.min(max[i][l-1], max[par][l-1]);
			}
		}
		
	}
	static void dfs(int u, int p,int idx) {
		edgeIdx[u]=idx;
		up[u][0] = p;
		for (int i = 1; i < log; i++) {
			if(up[u][i-1]==-1) {
				up[u][i]=-1;
				continue;
			}
			up[u][i] = up[up[u][i - 1]][i - 1];
			
		}
		for (edge e : adj2[u]) {
			int v=e.u;
			if (v != p) {
				level[v] = level[u] + 1;
				dfs(v, u,e.i);
			}
		}
	}
	static LinkedList<edge>[]adj2;
	static class edge{
		int u,i;
		edge(int v,int idx){
			u=v;i=idx;
		}
	}
	static int[]ans,edgeIdx;
	public static void main(String[] args) throws Exception{
		MScanner sc=new MScanner(System.in);
		PrintWriter pw=new PrintWriter(System.out);
		int n=sc.nextInt();
		adj=new LinkedList[n];
		for(int i=0;i<n;i++)adj[i]=new LinkedList<Integer>();
		adj2=new LinkedList[n];
		for(int i=0;i<n;i++)adj2[i]=new LinkedList<edge>();
		for(int i=0;i<n-1;i++) {
			int x=sc.nextInt()-1,y=sc.nextInt()-1;
			adj[x].add(y);
			adj[y].add(x);
			
			adj2[x].add(new edge(y,i));
			adj2[y].add(new edge(x, i));
		}
		up = new int[n][log];
		max=new int[n][log];
		level = new int[n];
		edgeIdx=new int[n];
		dfs(0, -1, -1);
		int m=sc.nextInt();
		ans=new int[n-1];
		int[][]cond=new int[m][3];
		for(int i=0;i<m;i++) {
			int l=sc.nextInt()-1,r=sc.nextInt()-1,val=sc.nextInt();
			update(l, r, val);
			cond[i][0]=l;cond[i][1]=r;cond[i][2]=val;
		}
		propagate();
		for(int i=0;i<m;i++) {
			int l=cond[i][0],r=cond[i][1],val=cond[i][2];
			int min=min(l, r);
			if(min!=val) {
				pw.println(-1);
				pw.flush();
				return;
			}
		}
		for(int i=1;i<n;i++) {
			int idx=edgeIdx[i];
			ans[idx]=max[i][0];
		}
		for(int i=0;i<n-1;i++) {
			pw.print(Math.max(1,ans[i])+" ");
		}
		pw.flush();
	}
	static class MScanner {
		StringTokenizer st;
		BufferedReader br;
		public MScanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}
 
		public MScanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int[] takearr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public long[] takearrl(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public Integer[] takearrobj(int n) throws IOException {
	        Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public Long[] takearrlobj(int n) throws IOException {
	        Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public String nextLine() throws IOException {
			return br.readLine();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
 
		public char nextChar() throws IOException {
			return next().charAt(0);
		}
 
		public Long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public boolean ready() throws IOException {
			return br.ready();
		}
 
		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}