Problem3380--Little Elephant and Tree

3380: Little Elephant and Tree

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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≤im) 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≤jn;ji), 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,vin,uivi), 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,bin,aibi), 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 

Source/Category