The Little Elephant loves trees very much, he especially loves root trees.

He's got a tree consisting of n nodes (the nodes are numbered from 1 to n), with root at node number 1. Each node of the tree contains some list of numbers which initially is empty. 

The Little Elephant wants to apply m operations. On the i-th operation (1 ≤ i ≤ m) he first adds number i to lists of all nodes of a subtree with the root in node number ai, and then he adds number i to lists of all nodes of the subtree with root in node bi.

After applying all operations the Little Elephant wants to count for each node i number ci — the number of integers j (1 ≤ j ≤ n; j ≠ i), such that the lists of the i-th and the j-th nodes contain at least one common number.

Help the Little Elephant, count numbers ci for him.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 105) — the number of the tree nodes and the number of operations. 

Each of the following n - 1 lines contains two space-separated integers, ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi), that mean that there is an edge between nodes number ui and vi. 

Each of the following m lines contains two space-separated integers, ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi), that stand for the indexes of the nodes in the i-th operation.

It is guaranteed that the given graph is an undirected tree.

Output

In a single line print n space-separated integers — c1, c2, ..., cn.

Examples

Input

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


Output

0 3 3 3 3 

Input

11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
2 9
3 6
2 8


Output

0 6 7 6 0 2 0 5 4 5 5 
// practice with rainboy
import java.io.*;
import java.util.*;

public class CF258E extends PrintWriter {
	CF258E() { super(System.out, true); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF258E o = new CF258E(); o.main(); o.flush();
	}

	int[] next, jj; int $ = 1;
	int[] ao, ll, rr, ii; int time;
	int link(int l, int j) {
		next[$] = l; jj[$] = j;
		return $++;
	}
	void init(int n, int m) {
		next = new int[1 + m * 2]; jj = new int[1 + m * 2];
		ao = new int[n];
		ll = new int[n]; rr = new int[n]; ii = new int[n];
	}
	void dfs(int p, int i) {
		ll[i] = time++;
		ii[ll[i]] = i;
		for (int l = ao[i]; l != 0; l = next[l]) {
			int j = jj[l];
			if (j != p)
				dfs(i, j);
		}
		rr[i] = time;
	}
	static class V {
		int l, r, y, pm;
		V(int l, int r, int y, int pm) {
			this.l = l; this.r = r; this.y = y; this.pm = pm;
		}
	}
	int[] tr, kk, sz; int n_;
	void build(int n) {
		n_ = 1;
		while (n_ < n)
			n_ <<= 1;
		tr = new int[n_ * 2]; kk = new int[n_ * 2]; sz = new int[n_ * 2];
		for (int i = 0; i < n; i++)
			sz[n_ + i] = 1;
		for (int i = n_ - 1; i > 0; i--)
			sz[i] = sz[i << 1] + sz[i << 1 | 1];
	}
	void pul(int i) {
		if (kk[i] > 0)
			tr[i] = sz[i];
		else
			tr[i] = i < n_ ? tr[i << 1] + tr[i << 1 | 1] : 0;
	}
	void put(int i, int x) {
		kk[i] += x;
		pul(i);
	}
	void pull(int i) {
		while (i > 1)
			pul(i >>= 1);
	}
	void update(int l, int r, int x) {
		int l_ = l += n_, r_ = r += n_;
		for ( ; l <= r; l >>= 1, r >>= 1) {
			if ((l & 1) == 1)
				put(l++, x);
			if ((r & 1) == 0)
				put(r--, x);
		}
		pull(l_); pull(r_);
	}
	void main() {
		int n = sc.nextInt();
		int m = sc.nextInt();
		init(n, n - 1);
		for (int h = 0; h < n - 1; h++) {
			int i = sc.nextInt() - 1;
			int j = sc.nextInt() - 1;
			ao[i] = link(ao[i], j);
			ao[j] = link(ao[j], i);
		}
		dfs(-1, 0);
		V[] vv = new V[m * 8];
		for (int h = 0; h < m; h++) {
			int i = sc.nextInt() - 1;
			int j = sc.nextInt() - 1;
			int li = ll[i], ri = rr[i], lj = ll[j], rj = rr[j];
			// [li, ri) x [li, ri)
			vv[h * 8 + 0] = new V(li, ri, li, 1);
			vv[h * 8 + 1] = new V(li, ri, ri, -1);
			// [li, ri) x [lj, rj)
			vv[h * 8 + 2] = new V(li, ri, lj, 1);
			vv[h * 8 + 3] = new V(li, ri, rj, -1);
			// [lj, rj) x [li, ri)
			vv[h * 8 + 4] = new V(lj, rj, li, 1);
			vv[h * 8 + 5] = new V(lj, rj, ri, -1);
			// [lj, rj) x [lj, rj)
			vv[h * 8 + 6] = new V(lj, rj, lj, 1);
			vv[h * 8 + 7] = new V(lj, rj, rj, -1);
		}
		Arrays.sort(vv, (u, v) -> u.y - v.y);
		build(n);
		int[] ans = new int[n];
		for (int y = 0, h = 0; y < n; y++) {
			V v;
			while (h < m * 8 && (v = vv[h]).y <= y) {
				update(v.l, v.r - 1, v.pm);
				h++;
			}
			ans[ii[y]] = Math.max(tr[1] - 1, 0);
		}
		for (int i = 0; i < n; i++)
			print(ans[i] + " ");
		println();
	}
}
