They say that Berland has exactly two problems, fools and roads. Besides, Berland has n cities, populated by the fools and connected by the roads. All Berland roads are bidirectional. As there are many fools in Berland, between each pair of cities there is a path (or else the fools would get upset). Also, between each pair of cities there is no more than one simple path (or else the fools would get lost). 

But that is not the end of Berland's special features. In this country fools sometimes visit each other and thus spoil the roads. The fools aren't very smart, so they always use only the simple paths.

A simple path is the path which goes through every Berland city not more than once.

The Berland government knows the paths which the fools use. Help the government count for each road, how many distinct fools can go on it.

Note how the fools' paths are given in the input.

Input

The first line contains a single integer n (2 ≤ n ≤ 105) — the number of cities. 

Each of the next n - 1 lines contains two space-separated integers ui, vi (1 ≤ ui, vi ≤ n, ui ≠ vi), that means that there is a road connecting cities ui and vi. 

The next line contains integer k (0 ≤ k ≤ 105) — the number of pairs of fools who visit each other. 

Next k lines contain two space-separated numbers. The i-th line (i > 0) contains numbers ai, bi (1 ≤ ai, bi ≤ n). That means that the fool number 2i - 1 lives in city ai and visits the fool number 2i, who lives in city bi. The given pairs describe simple paths, because between every pair of cities there is only one simple path.

Output

Print n - 1 integer. The integers should be separated by spaces. The i-th number should equal the number of fools who can go on the i-th road. The roads are numbered starting from one in the order, in which they occur in the input.

Examples

Input

5
1 2
1 3
2 4
2 5
2
1 4
3 5


Output

2 1 1 1 


Input

5
3 4
4 5
1 4
2 4
3
2 3
1 3
3 5


Output

3 1 1 1 

Note

In the first sample the fool number one goes on the first and third road and the fool number 3 goes on the second, first and fourth ones.

In the second sample, the fools number 1, 3 and 5 go on the first road, the fool number 5 will go on the second road, on the third road goes the fool number 3, and on the fourth one goes fool number 1.

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

/**
 *
 * @author Saju
 *
 */

public class Main {

//	static int[] dx = { 0, 1, 0, -1 };
//	static int[] dy = { -1, 0, 1, 0 };
//
//	static int[] ddx = { 0, 1, 0, -1, -1, 1, 1, -1 };
//	static int[] ddy = { -1, 0, 1, 0, -1, -1, 1, 1 };
//
//	static int[] kx = { 2, 1, -1, -2, -2, -1, 1, 2 };
//	static int[] ky = { 1, 2, 2, 1, -1, -2, -2, -1 };
//
//	static long MOD = Long.MAX_VALUE;
//
//	static final int MAX = 1000007;
//	static long INF = Long.MAX_VALUE;
//	static int INT_INF = Integer.MAX_VALUE;
//	static double PI = 3.1415926535;
//
//	private static final double EPSILON = 1e-10;
//
//	private static double dp[] = new double[MAX];

	private static Set<Integer> tree[];

	
	private static int MAXN = 300009; 
	private static int MAXA = 1000009;
	private static int BLOCK_SZ = 555;
	private static long answer = 0;
	private static int frequency[] = new int[MAXA];
	private static int arr[] = new int[MAXN];

	public static void main(String[] args) {

		InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		/*



 		
		*/
		
			int n = in.nextInt();
			
			List<Edge> adj[] = new ArrayList[n];
			for(int i = 0; i < n; i++){
				adj[i] = new ArrayList<Edge>();
			}
			for(int i = 0; i < n - 1; i++){
				int u = in.nextInt();
				int v = in.nextInt();
				u--;
				v--;
				adj[u].add(new Edge(u, v, i));
				adj[v].add(new Edge(v, u, i));
			}
			
			int[][] pp = new int[n][22];
			long[][] cost = new long[n][22];
			
			int log2n = log(n, 2) + 1;
			
			int parent[] = new int[n];
			int level[] = new int[n];
			Arrays.fill(parent, -1);
			Queue<Integer> queue = new LinkedList<Integer>();
			queue.add(0);
			boolean[] visited = new boolean[n];
			visited[0] = true;
			
			while(!queue.isEmpty()){
				int u = queue.remove();
				for(Edge e : adj[u]){
					if(!visited[e.v]){
						visited[e.v] = true;
						queue.add(e.v);
						parent[e.v] = u;
						level[e.v] = level[u] + 1;
						cost[e.v][0] = e.cost;
					}
				}
			}
			
			for(int i = 0; i < n; i++){
				pp[i][0] = parent[i];
			}
			
			for(int j = 1; j < log2n; j++){
				for(int i = 0; i < n; i++){
					if(pp[i][j - 1] != -1){
						pp[i][j] = pp[pp[i][j - 1]][j - 1];
					}
				}
			}
			
			int query = in.nextInt();
			StringBuilder sb = new StringBuilder();
			int val[] = new int[n];
//			sb.append("Case " + t + ":\n");
			for(int i = 0; i < query; i++){
				int u = in.nextInt();
				int v = in.nextInt();
				u--;
				v--;
				val[u]++;
				val[v]++;
				int lca = getLCA(n, u, v, parent, level, pp);
				val[lca] -= 2;
			}
			int edges[] = new int[n - 1];
//			System.out.println(Arrays.toString(val));
			solve(0, -1, -1, adj, val, edges);
			for(int i = 0; i < n-1; i++) {
				sb.append(edges[i]+" ");
			}
			
			out.println(sb.toString());
			
			
		out.flush();
		out.close();
		System.exit(0);
	}

	static int solve(int root, int edge, int parent,  List<Edge>[] adj, int[] val, int[] edges) {
		int sum = val[root];
		for(int i = 0; i < adj[root].size(); i++) {
			Edge e = adj[root].get(i);
			if(e.v != parent) {
				sum += solve(e.v, e.cost, root, adj, val, edges);
			}
		}
		if(edge != -1) edges[edge] = sum;
		return sum;
	}
	
	
	private static int getLCA(int n, int p, int q, int[] parent, int[] level, int[][] pp) {
		int log2n = log(n, 2) + 1;
		if(level[p] < level[q]){
			int temp = p;
			p = q;
			q = temp;
		}
		for(int j = log2n; j >= 0; j--){
			if ((level[p] - (1 << j)) >= level[q]) {
				p =  pp[p][j];
			}
		}
		
		if(p == q){
			return p;
		}
//		System.out.println((p + 1) + " " + (q + 1));
		
		for(int j = log2n; j >= 0; j--){
			if(pp[p][j] != pp[q][j]){
				p = pp[p][j];
				q = pp[q][j];
			}
		}
//		System.out.println(p + " " + q);
		
		return parent[p];
	}


	private static long getCost(int n, int p, int q, int[] level, long[][] cost, int[][] pp) {
		int log2n = log(n, 2) + 1;
		long sum = 0;
		if(level[p] < level[q]){
			int temp = p;
			p = q;
			q = temp;
		}
		for(int j = log2n; j >= 0; j--){
			if ((level[p] - (1 << j)) >= level[q]) {
				sum += cost[p][j];
				p =  pp[p][j];
			}
		}
		
		if(p == q){
			return sum;
		}
//		System.out.println((p + 1) + " " + (q + 1));
		
		for(int j = log2n; j >= 0; j--){
			if(pp[p][j] != pp[q][j]){
				sum += cost[p][j];
				sum += cost[q][j];
				p = pp[p][j];
				q = pp[q][j];
			}
		}
//		System.out.println(p + " " + q);
		sum += cost[p][0];
		sum += cost[q][0];
		return sum;
	}
	
	private static class Edge implements Comparable<Edge>{
		int u;
		int v;
		int cost;
		
		Edge(int u, int v, int cost){
			this.u = u;
			this.v = v;
			this.cost = cost;
		}

		@Override
		public int compareTo(Edge o) {
			
			return this.cost - o.cost;
		}
	}
	
	private static class Pair {
		int first;
		int second;

		Pair(int first, int second) {
			this.first = first;
			this.second = second;
		}
	}

	private static class Point {
		int x;
		int y;

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

		@Override
		public String toString() {

			return this.x + " " + this.y;
		}
	}

	private static int log(int x, int base)
	{
	    return (int) (Math.log(x) / Math.log(base));
	}
	
	// private static long set(long N, int pos) {
	//
	// return N = N | (1 << pos);
	// }
	// private static long check(long N, int pos) {
	//
	// return N & (1 << pos);
	// }
	// private static long reset(long N, int pos){
	//
	// return N=N|~(1<<pos);
	// }

	// nCk
	// private static long binomialCoeff(int n, int k){
	// long[] arr = new long[k + 1];
	// arr[0] = 1;
	// for(int i = 1; i <= n; i++){
	// for(int j = Math.min(i, k); j > 0; j--){
	// arr[j] = (arr[j] + arr[j - 1]) % MOD;
	// }
	// }
	// return arr[k];
	// }

	// BIT =>
	// https://www.hackerearth.com/practice/notes/binary-indexed-tree-or-fenwick-tree/
	// static int BIT[] = new int[MAX + 5];
	//
	// private static int query(int index) {
	// int sum = 0;
	// for (; index > 0; index -= (index & (-index))) {
	// sum += BIT[index];
	// }
	// return sum;
	// }
	//
	// private static void update(int size, int index, int val) {
	// for (; index <= size; index += (index & (-index))) {
	// BIT[index] += val;
	// }
	// }

	/*
	 * 
	 * tutorial :
	 * https://helloacm.com/algorithms-series-0-1-backpack-dynamic-programming-
	 * and-backtracking/
	 * 
	 */

	// here arr and prob zero based index
	// static int backPack(int n, int m, int[] arr, double[] prob, double p) {
	// double dp[][] = new double[n + 1][m + 1];
	// for (int i = 0; i <= n; ++i) {
	// dp[i][0] = 1.0;
	// }
	// for (int i = 1; i <= n; i++) {
	// for (int j = 1; j <= m; j++) {
	//
	// if (j < arr[i - 1]) { // insufficient capacity
	// dp[i][j] = dp[i - 1][j];
	// } else {
	// dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - arr[i - 1]] * (1.0 -
	// prob[i - 1]));
	// }
	//
	// }
	// }
	// for (int i = m; i >= 0; i--) { // reverse checking the maximum weight
	// if ((1.0 - dp[n][i]) <= p) {
	// return i;
	// }
	// }
	// return 0;
	// }

	// here arr and prob one based index
	// static int backPack1(int n, int m, int[] arr, double[] prob, double p) {
	//
	// double dp[] = new double[m + 1];
	//
	// dp[0] = 1.0;
	// for (int i = 1; i <= n; i++) {
	// for (int j = m; j >= arr[i]; --j) {
	// // dp[j] = dp[j] || dp[j - A[i - 1]];
	// dp[j] = Math.max(dp[j], dp[j - arr[i]] * (1.0 - prob[i]));
	// }
	// }
	// for (int i = m; i >= 0; i--) {
	// if (1.0 - dp[i] <= p) {
	// return i;
	// }
	// }
	// return 0;
	// }

	/*
	 *
	 * tutorial :
	 * https://www.hackerearth.com/practice/algorithms/searching/ternary-search/
	 * tutorial/
	 *
	 */

	// lightoj -> 1146
	// static double ternary(Point a, Point b, Point c, Point d) {
	//
	// double l = 0;
	// double r = 1;
	//
	// for (int i = 0; i < 200; i++) {
	// double mid1 = l + ((r - l) / 3);
	// double mid2 = r - ((r - l) / 3);
	//
	// double dis1 = func(a, b, c, d, mid1);
	// double dis2 = func(a, b, c, d, mid2);
	//
	// if(dis1 > dis2){
	// l = mid1;
	//
	// }
	// else{
	// r = mid2;
	// }
	// }
	//
	// return l;
	//
	// }
	//
	// static double func(Point a, Point b, Point c, Point d, double multiple) {
	//
	// double xDifAB = b.x - a.x;
	// double yDifAB = b.y - a.y;
	// double xDifCD = d.x - c.x;
	// double yDifCD = d.y - c.y;
	//
	// double x1 = a.x + xDifAB * multiple;
	// double y1 = a.y + yDifAB * multiple;
	// double x2 = c.x + xDifCD * multiple;
	// double y2 = c.y + yDifCD * multiple;
	//
	// double distance = Math.sqrt(((x1 - x2) * (x1 - x2)) +
	// ((y1 - y2) * (y1 - y2)));
	//
	// return distance;
	// }
	//
	// static class Point{
	// double x;
	// double y;
	//
	// Point(double x, double y){
	// this.x = x;
	// this.y = y;
	// }
	// }

	// static void primeFactorization(int n) {
	// int temp = n;
	// Map<Integer, Integer> map = new HashMap<Integer, Integer>();
	// for (int i = 2; i <= Math.sqrt(n); i++) {
	// if (n % i == 0) {
	// int count = 0;
	// while (n % i == 0) {
	// count++;
	// n = n / i;
	// }
	// System.out.println("i: " + i + ", count: " + count);
	// map.put(i, count);
	// }
	//
	// }
	// if (n != 1) {
	// System.out.println(n);
	// map.put(n, 1);
	// }
	//
	//// calculateSumOfDivisor(map, temp);
	// }

	// static int counter[] = new int[MAX];
	//
	// private static void calculateSumOfDivisor(Map<Integer, Integer> map, int
	// n) {
	// int sum = 1;
	// for(Integer key : map.keySet()){
	// int count = map.get(key);
	// sum *= ((Math.pow(key, count + 1) - 1) / (key - 1));
	// }
	// if(sum < MAX){
	// if(counter[sum] < n){
	//// System.out.println("H");
	// counter[sum] = n;
	// }
	//
	// }
	//
	//// System.out.println(sum);
	// }

	// static int phi[] = new int[MAX];
	// static int phiStepCount[] = new int[MAX];
	// static void computeTotient() {
	//
	// // Create and initialize an array to store
	// // phi or totient values
	// for (int i = 1; i < MAX; i++) {
	// phi[i] = i; // indicates not evaluated yet
	// // and initializes for product
	// // formula.
	// }
	//
	// // Compute other Phi values
	// for (int p = 2; p < MAX; p++) {
	//
	// // If phi[p] is not computed already,
	// // then number p is prime
	// if (phi[p] == p) {
	//
	// // Phi of a prime number p is
	// // always equal to p-1.
	// phi[p] = p - 1;
	//
	// // Update phi values of all
	// // multiples of p
	// for (int i = 2 * p; i < MAX; i += p) {
	//
	// // Add contribution of p to its
	// // multiple i by multiplying with
	// // (1 - 1/p)
	// phi[i] = (phi[i] / p) * (p - 1);
	// }
	//
	// // for (int i = p; i < MAX; i += p) {
	// //
	// // phi[i] -= (phi[i] / p);
	// // }
	//
	// }
	//// phiStepCount[p] = phiStepCount[phi[p]] + 1;
	// }
	//
	//// for(int i = 1; i < MAX; i++){
	//// phiStepCount[i] += phiStepCount[i - 1];
	//// }
	// }

	// public static BigInteger floorOfNthRoot(BigInteger x, int n) {
	// int sign = x.signum();
	// if (n <= 0 || (sign < 0))
	// throw new IllegalArgumentException();
	// if (sign == 0)
	// return BigInteger.ZERO;
	// if (n == 1)
	// return x;
	// BigInteger a;
	// BigInteger bigN = BigInteger.valueOf(n);
	// BigInteger bigNMinusOne = BigInteger.valueOf(n - 1);
	// BigInteger b = BigInteger.ZERO.setBit(1 + x.bitLength() / n);
	// do {
	// a = b;
	// b = a.multiply(bigNMinusOne).add(x.divide(a.pow(n - 1))).divide(bigN);
	// } while (b.compareTo(a) == -1);
	// return a;
	// }

	// O(log(max(A, B))).
	// static long gcd(long a, long b) {
	// if (b == 0)
	// return a;
	// return gcd(b, a % b);
	// }

	private static double getDistance(double x1, double y1, double x2, double y2) {

		return Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));
	}

	// private static int getDecimal(String str) {
	// int val = 0;
	//
	// for (int i = str.length() - 1, j = 0; i >= 0; i--, j++) {
	// if (str.charAt(i) == '1') {
	// val += Math.pow(2, j);
	// }
	// }
	// return val;
	// }

	// private static int call(int i, int j, int[][] colors) {
	//
	// if (i >= colors.length) {
	// return 0;
	// }
	//
	// if (dp[i][j] != -1) {
	// return dp[i][j];
	//
	// }
	//
	// int result = Integer.MAX_VALUE;
	//
	// for (int k = 0; k < 3; k++) {
	// if (k == j) {
	// continue;
	// } else {
	// result = Math.min(result, call(i + 1, k, colors) + colors[i][j]);
	// }
	// }
	//
	// return dp[i][j] = result;
	// }

	// static int dp[][];

	// private static BigInteger fac(int n, int mod) {
	//
	// if (n <= 0) {
	// return BigInteger.ONE;
	// }
	// return BigInteger.valueOf(n).multiply(fac(n - 1, mod));
	// }

	// private static long modInverse(long n, long m){
	// return bigMod(n, m - 2, m);
	// }

	// private static long bigMod(long n, long k, long m) {
	//
	// long ans = 1;
	// while (k > 0) {
	// if ((k & 1) == 1) {
	// ans = (ans * n) % m;
	// }
	// n = (n * n) % m;
	// k >>= 1;
	// }
	// return ans;
	// }

	// Returns an iterator pointing to the first element
	// in the range [first, last] which does not compare less than val.
	// private static int lowerBoundNew(long[] arr, long num){
	// int start = 0;
	// int end = arr.length - 1;
	// int index = 0;
	// int len = arr.length;
	// int mid = 0;
	// while(true){
	// if(start > end){
	// break;
	// }
	// mid = (start + end) / 2;
	// if(arr[mid] > num){
	// end = mid - 1;
	// }
	// else if(arr[mid] < num){
	// start = mid + 1;
	// }
	// else{
	// while(mid >= 0 && arr[mid] == num){
	// mid--;
	// }
	// return mid + 1;
	// }
	// }
	// if(arr[mid] < num){
	// return mid + 1;
	// }
	// return mid;
	// }

	// upper_bound() is a standard library function
	// in C++ defined in the header .
	// It returns an iterator pointing to
	// the first element in the range [first, last)
	// that is greater than value, or last if no such element is found
	// private static int upperBoundNew(long[] arr, long num){
	//
	// int start = 0;
	// int end = arr.length - 1;
	// int index = 0;
	// int len = arr.length;
	// int mid = 0;
	// while(true){
	// if(start > end){
	// break;
	// }
	// mid = (start + end) / 2;
	// if(arr[mid] > num){
	// end = mid - 1;
	// }
	// else if(arr[mid] < num){
	// start = mid + 1;
	// }
	// else{
	// while(mid < len && arr[mid] == num){
	// mid++;
	// }
	// if(mid == len - 1 && arr[mid] == num){
	// return mid + 1;
	// }
	// else{
	// return mid;
	// }
	// }
	// }
	// if(arr[mid] < num){
	// return mid + 1;
	// }
	// return mid;
	// }

	// private static int upperBound(long[] arr, long num) {
	//
	// int start = 0;
	// int end = arr.length;
	//
	// int mid = 0;
	// int index = 0;
	// while (true) {
	//
	//// System.out.println(start + " " + end);
	// if (start > end) {
	// break;
	// }
	// mid = (start + end) / 2;
	// if (arr[mid] > num) {
	// end = mid - 1;
	//
	// } else if (arr[mid] < num) {
	// start = mid + 1;
	// } else {
	// return mid;
	// }
	//
	//// System.out.println("a: " + start + " " + end);
	// }
	//
	// // System.out.println(mid);
	// if (arr[mid] < num) {
	// index = mid + 1;
	// } else {
	// index = mid;
	// }
	// return index;
	// }

	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}

		public String next() {
			try {
				while (tokenizer == null || !tokenizer.hasMoreTokens()) {
					tokenizer = new StringTokenizer(reader.readLine());

				}
			} catch (IOException e) {
				return null;
			}
			return tokenizer.nextToken();
		}

		public String nextLine() {
			String line = null;
			try {
				tokenizer = null;
				line = reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
			return line;
		}

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

		public double nextDouble() {
			return Double.parseDouble(next());
		}

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

		public boolean hasNext() {
			try {
				while (tokenizer == null || !tokenizer.hasMoreTokens()) {
					tokenizer = new StringTokenizer(reader.readLine());
				}
			} catch (Exception e) {
				return false;
			}
			return true;
		}
	}
}

	  			 			 			 		   		 	  					