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 R617F
{
	
	static int n;
	static ArrayList<Edge>[] tree;

	static int[] depth;
	static int[] par;
	static int[] lo;
	static int[] hi;
	static int[] parEdgeID;
	
	public static void main(String[] args)
	{
		JS scan = new JS();
		PrintWriter out = new PrintWriter(System.out);
		n = scan.nextInt();
		tree = new ArrayList[n];
		for(int i = 0; i < n; i++) tree[i] = new ArrayList<Edge>();
		for(int i = 0; i < n-1; i++) {
			int u = scan.nextInt()-1;
			int v = scan.nextInt()-1;
			tree[u].add(new Edge(v, i));
			tree[v].add(new Edge(u, i));
		}
		
		int m = scan.nextInt();
		Query[] qarr = new Query[m];
		for(int i = 0; i < m; i++) 
			qarr[i] = new Query(scan.nextInt()-1, scan.nextInt()-1, scan.nextInt());
		Arrays.sort(qarr);
		
		depth = new int[n];
		par = new int[n];
		hi = new int[n];
		lo = new int[n];
		parEdgeID = new int[n];
		
		int[] ans = new int[n-1];
		
		Arrays.fill(par, -1);
		Arrays.fill(parEdgeID, -1);
		Arrays.fill(ans, 1000000);
		dfs(0);
//		System.out.println(Arrays.toString(par));
//		System.out.println(Arrays.toString(depth));
//		System.out.println(Arrays.toString(parEdgeID));
//		System.out.println(Arrays.toString(lo));
//		System.out.println(Arrays.toString(hi));
		
		for(int qq = 0; qq < m; qq++) {
			Query q = qarr[qq];
			int u = q.u;
			int v = q.v;
			int w = q.min;
			
			if(lo[u] <= lo[v] && hi[u] >= lo[v]) {
				while(u != v) {
					ans[parEdgeID[v]] = w;
					v = par[v];
				}
			}
			else if(lo[v] <= lo[u] && hi[v] >= lo[u]) {
				while(u != v) {
					ans[parEdgeID[u]] = w;
					u = par[u];
				}
			}
			else { // bring u and v up to their lca
				while(depth[u] > depth[v]) {
					ans[parEdgeID[u]] = w;
					u = par[u];
				}
				while(depth[v] > depth[u]) {
					ans[parEdgeID[v]] = w;
					v = par[v];
				}
				while(u != v) {
					ans[parEdgeID[v]] = w;
					v = par[v];
					ans[parEdgeID[u]] = w;
					u = par[u];
				}
			}
		}
//		System.out.println(Arrays.toString(ans));
		
		for(int qq = 0; qq < m; qq++) {
			Query q = qarr[qq];
			int u = q.u;
			int v = q.v;
			int w = q.min;
			
			int min = Integer.MAX_VALUE;
			if(lo[u] <= lo[v] && hi[u] >= lo[v]) {
				while(u != v) {
					min = Math.min(ans[parEdgeID[v]], min);
					v = par[v];
				}
			}
			else if(lo[v] <= lo[u] && hi[v] >= lo[u]) {
				while(u != v) {
					min = Math.min(ans[parEdgeID[u]], min);
					u = par[u];
				}
			}
			else {
				while(depth[u] > depth[v]) {
					min = Math.min(ans[parEdgeID[u]], min);
					u = par[u];
				}
				while(depth[v] > depth[u]) {
					min = Math.min(ans[parEdgeID[v]], min);
					v = par[v];
				}
				while(u != v) {
					min = Math.min(ans[parEdgeID[v]], min);
					v = par[v];
					min = Math.min(ans[parEdgeID[u]], min);
					u = par[u];
				}
			}
//			System.out.println(u+" "+v);
//			System.out.println(q.u+" "+q.v+" "+q.min+" "+min);
			if(min != w) {
				System.out.println(-1);
				return;
			}
		}
		
		for(int i = 0; i < n-1; i++) out.print(ans[i]+" ");
		out.flush();
	}
	
	static int idx = 1;
	
	static void dfs(int curr) {
		for(Edge e : tree[curr]) {
			int to = e.to;
			if(to != par[curr]) {
				depth[to] = depth[curr]+1;
				parEdgeID[to] = e.i;
				lo[to] = idx++;
				par[to] = curr;
				dfs(to);
			}
		}
		hi[curr] = idx++;
	}
	
	static class Edge{
		
		int to;
		int i;
		
		public Edge(int to, int i) {
			this.to = to;
			this.i = i;
		}
	}
	
	static class Query implements Comparable<Query>{
		
		int u;
		int v;
		int min;
		
		public Query(int u, int v, int min) {
			this.u = u;
			this.v = v;
			this.min = min;
		}

		@Override
		public int compareTo(Query o)
		{
			return this.min-o.min;
		}
	}

	static class JS{
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public JS() {
			in = new BufferedInputStream(System.in, BS);
		}

		public JS(String s) throws FileNotFoundException {
			in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}				
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
	}

}