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 
import java.io.*;
import java.util.*;
import java.math.*;

import javax.management.RuntimeErrorException;

import static java.lang.Math.*;

public class Main implements Runnable {
    
	final boolean file = false;
	
	ArrayList<Integer> g[];
	ArrayList<Integer> q[];
	SegmentTree t;
	int time = 0;
	int inTime[],outTime[];
	int res[];
	
	void dfs(int v, int p) {
		inTime[v] = time++;
		for (int i = 0; i < g[v].size(); i++) {
			int to = g[v].get(i);
			if (to == p) continue;
			dfs(to,v);
		}
		outTime[v] = time++;
	}
	
	void go(int v, int p) {
		for (int i = 0; i < q[v].size(); i++) {
			int w = q[v].get(i);
			t.add(inTime[w],outTime[w],1);
		}
		res[v] = t.cnt[1];
		if (t.t[1] != 0) res[v] = 0;
		res[v] = (time - res[v]) / 2;
		if (t.get(inTime[v]) != 0) res[v]--;
		for (int i = 0; i < g[v].size(); i++) {
			int to = g[v].get(i);
			if (to == p) continue;
			go(to,v);
		}
		for (int i = 0; i < q[v].size(); i++) {
			int w = q[v].get(i);
			t.add(inTime[w],outTime[w],-1);
		}
	}
	
	void solve() throws Exception {
		int n = sc.nextInt();
		int m = sc.nextInt();
		g = new ArrayList[n];
		q = new ArrayList[n];
		res = new int[n];
		inTime = new int[n];
		outTime = new int[n];
		for (int i = 0; i < n; i++) {
			g[i] = new ArrayList<Integer>();
			q[i] = new ArrayList<Integer>();
		}
		for (int i = 0; i < n - 1; i++) {
			int a = sc.nextInt() - 1;
			int b = sc.nextInt() - 1;
			g[a].add(b);
			g[b].add(a);
		}
		dfs(0,-1);
		t = new SegmentTree(time);
		for (int i = 0; i < m; i++) {
			int a = sc.nextInt() - 1;
			int b = sc.nextInt() - 1;
			q[a].add(a);
			q[a].add(b);
			q[b].add(a);
			q[b].add(b);
		}		
		go(0,-1);
		for (int i = 0; i < n; i++) {
			out.print(res[i] + " ");
		}
    }
    
    BufferedReader in;
    PrintWriter out;
    FastScanner sc;
    
    static Throwable uncaught;
    
    public void run() {
        try {
        	if (file) {
        		in = new BufferedReader(new FileReader("domino.in"));
                out = new PrintWriter(new FileWriter("domino.out"));
        	} else {
        		in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
        	}
            sc = new FastScanner(in);
            solve();
        } catch (Throwable t) {
            Main.uncaught = t;
        } finally {
            out.close();
        }
    }
    
    public static void main(String[] args) throws Throwable {
        Thread t = new Thread(null, new Main(), "", 128 * 1024 * 1024);
        t.start();
        t.join();
        if (uncaught != null) {
            throw uncaught;
        }
    }

}

class FastScanner {
    
    BufferedReader reader;
    StringTokenizer strTok;
    
    public FastScanner(BufferedReader reader) {
        this.reader = reader;
    }
    
    public String nextToken() throws IOException {
        while (strTok == null || !strTok.hasMoreTokens()) {
            strTok = new StringTokenizer(reader.readLine());
        }
        return strTok.nextToken();
    }
    
    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }
    
    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
    
    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
    
}

class SegmentTree {
	
	int n;
	int t[],add[],cnt[];
	
	public SegmentTree(int n) {
		this.n = n;
		this.t = new int[4 * n];
		this.add = new int[4 * n];
		this.cnt = new int[4 * n];
		buildTree(0,n - 1,1);
	}
	
	void relax(int idx) {
		if (t[2 * idx] < t[2 * idx + 1]) {
			t[idx] = t[2 * idx];
			cnt[idx] = cnt[2 * idx];
		} else if (t[2 * idx] > t[2 * idx + 1]) {
			t[idx] = t[2 * idx + 1];
			cnt[idx] = cnt[2 * idx + 1];
		} else {
			t[idx] = t[2 * idx];
			cnt[idx] = cnt[2 * idx] + cnt[2 * idx + 1];
		}
	}
	
	void buildTree(int l, int r, int idx) {
		if (l == r) {
			t[idx] = 0;
			cnt[idx] = 1;
			add[idx] = 0;
		} else {
			int mid = (l + r) >> 1;
			buildTree(l,mid,2 * idx);
			buildTree(mid + 1,r,2 * idx + 1);
			relax(idx);
		}
	}
	
	void push(int idx) {
		if (add[idx] != 0) {
			add[2 * idx] += add[idx];
			add[2 * idx + 1] += add[idx];
			t[2 * idx] += add[idx];
			t[2 * idx + 1] += add[idx];
			add[idx] = 0;
		}
	}
	
	int get(int pos) {
		return get(0,n - 1,pos,1);
	}
	
	int get(int l, int r, int pos, int idx) {
		if (l == r) return t[idx];
		push(idx);
		int mid = (l + r) >> 1;		
		if (pos <= mid) return get(l,mid,pos,2 * idx);
		return get(mid + 1,r,pos,2 * idx + 1);
	}
	
	void add(int a, int b, int val) {
		add(0,n - 1,a,b,1,val);
	}
	
	void add(int l, int r, int a, int b, int idx, int val) {
		if (b < l || r < a) return;
		if (a <= l && r <= b) {
			add[idx] += val;
			t[idx] += val;
		} else {
			push(idx);
			int mid = (l + r) >> 1;
			add(l,mid,a,b,2 * idx,val);
			add(mid + 1,r,a,b,2 * idx + 1,val);
			relax(idx);
		}
	}	
	 
}