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 $*a*_{*i*}$, and then he adds number $*i*$ to lists of all nodes of the subtree with root in node $*b*_{*i*}$.

After applying all operations the Little Elephant wants to count for each node $*i*$ number $*c*_{*i*}$ — 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 $*c*_{*i*}$ for him.

Input

The first line contains two integers $*n*$ and $*m*$ $(1 ≤ *n*, *m* ≤ 10^{5})$ — the number of the tree nodes and the number of operations.

Each of the following $*n* - 1$ lines contains two space-separated integers, $*u*_{*i*}$ and $*v*_{*i*}$ $(1 ≤ *u*_{*i*}, *v*_{*i*} ≤ *n*, *u*_{*i*} ≠ *v*_{*i*})$, that mean that there is an edge between nodes number $*u*_{*i*}$ and $*v*_{*i*}$.

Each of the following $*m*$ lines contains two space-separated integers, $*a*_{*i*}$ and $*b*_{*i*}$ $(1 ≤ *a*_{*i*}, *b*_{*i*} ≤ *n*, *a*_{*i*} ≠ *b*_{*i*})$, 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 — $*c*_{1}, *c*_{2}, ..., *c*_{*n*}$.