258_E. Little Elephant and Tree_36711
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.BufferedReader;
import java.util.Comparator;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Collection;
import java.util.List;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE {
    Graph tree;
    DFSOrder dfsOrder;
    int[] parent;
    List<Event>[] events;

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int n = in.nextInt();
        int nQueries = in.nextInt();
        tree = new Graph();
        tree.initGraph(n, n-1);
        for (int i = 0; i < n-1; ++i) {
            int x = in.nextInt() - 1;
            int y = in.nextInt() - 1;
            tree.addEdge(x, y);
        }
        parent = Parent.run(tree, 0);
        dfsOrder = new DFSOrder(tree, 0, parent);
        int[] order = new int[n];
        for (int i = 0; i < n; ++i) {
            order[dfsOrder.start(i)] = i;
        }
        SegmentTree sTree = new SegmentTree(n + 1);
//        for (int i = 0; i < n; ++i) {
//            out.println(i + " " + dfsOrder.start(i) + " " + dfsOrder.end(i));
//        }
        events = new List[n+1];
        for (int i = 0; i <= n; ++i) {
            events[i] = new ArrayList<Event>();
        }
        while (nQueries-- > 0) {
            int v1 = in.nextInt() - 1;
            int v2 = in.nextInt() - 1;
            int left1 = dfsOrder.start(v1);
            int right1 = dfsOrder.end(v1);
            int left2 = dfsOrder.start(v2);
            int right2 = dfsOrder.end(v2);
            events[left1].add(new Event(1, left1, right1));
            events[left1].add(new Event(1, left2, right2));

            events[left2].add(new Event(1, left1, right1));
            events[left2].add(new Event(1, left2, right2));

            events[right1 + 1].add(new Event(0, left1, right1));
            events[right2 + 1].add(new Event(0, left1, right1));

            events[right1 + 1].add(new Event(0, left2, right2));
            events[right2 + 1].add(new Event(0, left2, right2));
        }
        int[] res = new int[n];
        for (int i = 0; i < n; ++i) {
            Collections.sort(events[i]);
            for (Event e : events[i]) {
                if (e.type == 0) {
                    sTree.delete(e.left, e.right);
                } else {
                    sTree.add(e.left, e.right);
                }
            }

            res[order[i]] = sTree.maxRight + 1 - sTree.get0();
            if (res[order[i]] > 0) --res[order[i]];
        }
        out.println(ArrayUtils.toString(res));
    }

    class Event implements Comparable<Event> {
        int type;
        int left, right;

        Event(int type, int left, int right) {
            this.type = type;
            this.left = left;
            this.right = right;
        }

        public int compareTo(Event event) {
            if (type != event.type) return type - event.type;
            if (left != event.left) return left - event.left;
            return right - event.right;
        }
    }

    class SegmentTree {
        int[] min;
        int[] cnt;
        int[] add;
        int maxTree, maxRight;

        SegmentTree(int size) {
            maxTree = 1;
            while (maxTree <= size) maxTree <<= 1;
            maxRight = maxTree - 1;
            maxTree <<= 1;
            min = new int[maxTree];
            cnt = new int[maxTree];
            add = new int[maxTree];
            initTree(1, 0, maxRight);
        }

        private void initTree(int v, int left, int right) {
            min[v] = 0;
            add[v] = 0;
            cnt[v] = right - left + 1;
            if (left != right) {
                int middle = (left + right) / 2;
                initTree(v * 2, left, middle);
                initTree(v * 2 + 1, middle + 1, right);
            }
        }

        void add(int left, int right) {
            internalUpdate(1, 0, maxRight, left, right, 1);
        }

        void delete(int left, int right) {
            internalUpdate(1, 0, maxRight, left, right, -1);
        }

        private void internalUpdate(int v, int rangeLeft, int rangeRight, int left, int right, int value) {
            if (rangeLeft == left && rangeRight == right) {
                add[v] += value;
                return;
            }
            int middle = (rangeLeft + rangeRight) / 2;
            if (left <= middle) internalUpdate(v * 2, rangeLeft, middle, left, Math.min(right, middle), value);
            if (right > middle) internalUpdate(v * 2 + 1, middle + 1, rangeRight, Math.max(middle + 1, left), right, value);
            min[v] = Math.min(min[v * 2] + add[v * 2], min[v * 2 + 1] * add[v * 2 + 1]);
            cnt[v] = 0;
            if (min[v] == min[v * 2] + add[v * 2]) {
                cnt[v] += cnt[v * 2];
            }
            if (min[v] == min[v * 2 + 1] + add[v * 2 + 1]) {
                cnt[v] += cnt[v * 2 + 1];
            }
        }

        int get0() {
            int m = min[1] + add[1];
            if (m == 0) {
                return cnt[1];
            }
            return 0;
        }
    }
}

class Graph {
    public int[] from;
    public int[] to;
    public int[] first;
    public int[] next;
    public int nVertex;
    public int nEdges;
    public int curEdge;

    public Graph() {}

    public void initGraph(int n, int m) {
        curEdge = 0;
        nVertex = n;
        nEdges = m;
        from = new int[m * 2];
        to = new int[m * 2];
        first = new int[n];
        next = new int[m * 2];
        Arrays.fill(first, -1);
    }

    public void addEdge(int a, int b) {
        next[curEdge] = first[a];
        first[a] = curEdge;
        to[curEdge] = b;
        from[curEdge] = a;
        ++curEdge;

        next[curEdge] = first[b];
        first[b] = curEdge;
        to[curEdge] = a;
        from[curEdge] = b;
        ++curEdge;
    }

}

class DFSOrder {
    int[] start;
    int[] end;

    public DFSOrder(Graph tree, int root, int[] p) {
        start = new int[tree.nVertex];
        end = new int[tree.nVertex];
        buildDfsOrder(tree, root, p);
    }

    public int start(int v) {
        return start[v];
    }

    public int end(int v) {
        return end[v];
    }

    private void buildDfsOrder(Graph tree, int root, int[] p) {
        int[] stack = new int[2 * tree.nVertex];
        int top = 0;
        stack[top++] = (root + 1);
        int time = 0;
        while (top > 0) {
            --top;
            int v = stack[top];
            if (v < 0) {
                v = (-v) - 1;
                end[v] = time-1;
            } else {
                --v;
                start[v] = time++;
                stack[top++] = -(v+1);
                for (int i = tree.first[v]; i != -1; i = tree.next[i]) {
                    if (p[v] != tree.to[i]) {
                        stack[top++] = (tree.to[i] + 1);
                    }
                }
            }
        }
    }
}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer stt;

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

    public String nextLine() {
        try {
            return reader.readLine().trim();
        } catch (IOException e) {
            return null;
        }
    }

    public String nextString() {
        while (stt == null || !stt.hasMoreTokens()) {
            stt = new StringTokenizer(nextLine());
        }
        return stt.nextToken();
    }

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

}

class Parent {
    public static int[] run(Graph tree, int root) {
        int[] parent = new int[tree.nVertex];
        int[] queue = new int[tree.nVertex];
        int front = 0, back = 0;
        queue[back++] = root;
        parent[root] = -1;
        while (front < back) {
            int v = queue[front++];
            for (int i = tree.first[v]; i != -1; i = tree.next[i]) {
                if (parent[v] != tree.to[i]) {
                    queue[back++] = tree.to[i];
                    parent[tree.to[i]] = v;
                }
            }
        }
        return parent;
    }

}

class ArrayUtils {

    public static String toString(int[] a) {
        StringBuilder result = new StringBuilder("");
        for (int x : a) result.append(x).append(' ');
        return result.substring(0, result.length()-1);
    }

}


5 1
1 2
1 3
3 5
3 4
2 3
 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
 11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
4 9
3 6
2 8
 11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
3 9
3 6
2 8
 11 3
1 3
2 3
2 4
1 5
7 6
5 7
5 8
6 9
8 10
8 11
3 9
3 6
2 8
 11 3
1 2
2 3
2 4
1 5
5 6
4 7
5 8
6 9
8 10
8 11
2 9
3 6
2 8
 11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
3 9
3 9
2 8
 11 3
1 3
2 3
2 4
1 5
4 6
5 7
5 8
6 9
8 10
8 11
3 9
3 6
2 8
 11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
4 9
3 9
2 8
 11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
3 9
3 6
1 8
 5 1
1 2
1 3
3 5
3 4
2 1
 11 3
1 3
2 3
2 4
1 8
7 6
5 7
5 8
6 9
8 10
8 11
3 9
3 6
2 8
 11 3
1 2
2 3
3 4
1 5
5 6
4 7
5 8
6 9
8 10
8 11
2 9
3 6
2 8
 11 3
1 3
2 3
2 4
1 8
7 6
5 7
5 8
6 9
8 10
8 11
3 9
5 6
2 8
 5 1
1 2
1 3
3 5
5 4
2 3
 11 3
1 2
2 3
2 4
1 10
5 6
5 7
5 8
6 9
8 10
8 11
3 9
3 6
2 8
 11 3
1 3
2 3
2 4
1 5
4 6
5 7
5 8
6 9
8 10
8 11
3 9
3 6
3 8
 11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
4 11
3 6
2 2
 11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
5 10
8 11
4 9
3 6
2 8
 11 3
1 4
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
3 9
3 6
2 8
 11 3
1 2
2 3
2 4
1 5
5 6
8 7
5 8
6 9
8 10
8 11
3 9
3 9
2 8
 11 3
1 2
2 3
3 4
2 5
5 6
4 7
5 8
6 9
8 10
8 11
2 9
3 6
2 8
 11 3
1 2
2 3
2 4
1 8
5 6
5 7
5 8
6 9
8 10
8 11
4 11
3 9
2 4
 5 1
1 2
1 3
3 5
3 4
2 4
 11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
3 7
3 6
2 8
 11 3
1 3
2 3
2 4
1 5
7 6
5 7
5 8
6 9
8 10
8 11
3 9
5 6
2 8
 11 3
1 2
2 3
2 4
1 5
7 6
5 7
5 8
6 9
8 10
8 11
3 9
3 6
2 8
 11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
4 11
3 6
2 8
 11 3
1 2
2 3
2 4
1 5
7 6
5 7
5 8
6 9
8 10
8 11
3 9
1 6
2 8
 11 3
1 2
2 3
2 4
1 10
5 6
5 7
5 8
6 9
8 10
8 11
3 9
3 6
2 1
 11 3
1 3
2 3
2 4
1 5
4 6
5 7
5 8
6 9
8 10
8 11
3 9
6 6
2 8
 11 3
1 2
2 3
2 4
1 5
5 6
5 7
7 8
6 9
8 10
8 11
4 9
3 9
2 8
 11 3
1 3
2 3
2 4
1 8
7 6
5 7
5 11
6 9
8 10
8 11
3 9
5 6
2 8
 11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
4 11
3 6
2 4
 11 3
1 2
2 3
2 4
1 5
5 6
5 7
4 8
6 9
8 10
8 11
4 11
3 6
2 2
 11 3
1 2
2 3
2 4
1 5
5 6
8 7
5 8
6 9
11 10
8 11
3 9
3 9
2 8
 11 3
1 2
2 3
2 4
1 5
8 6
5 7
7 8
6 9
8 10
8 11
4 9
3 9
2 8
 11 3
1 2
2 3
2 4
1 8
5 6
5 7
5 8
6 9
8 10
8 11
4 11
3 6
2 4
 11 3
1 3
2 3
2 4
1 5
7 6
5 7
5 8
6 9
8 10
8 11
3 9
1 6
2 8
 11 3
1 2
2 3
2 4
1 5
5 6
1 7
5 8
6 9
8 10
8 11
3 9
3 6
1 8
 5 1
1 2
1 3
2 5
5 4
2 3

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