No.3309 Aging Railway
Note
The time limit for this problem is 3000ms.
Problem Statement
Railway Y, which runs in the Kingdom of yu23578, has $N$ stations, numbered from $1$ to $N$.
Railway Y also has $N-1$ tracks, numbered from $1$ to $N-1$. Track $i (1 \le i \le N-1)$ connects station $u_i$ and station $v_i$ bidirectionally, and trains run on it.
There are $M$ office workers using Railway Y, and the $j (1 \le j \le M)$-th office worker commutes from station $s_j$, the nearest station to their home, to station $t_j$, the nearest station to their company.
However, because Railway Y is aging, it is known that track $k$ will be abolished $k (1 \le k \le N-1)$ years from now, and an abolished track can no longer be used.
For each $k = 1,2,3,\cdots ,N-1$, find the answer to the following question $:$
・ How many office workers can commute by Railway Y from the nearest station to their home to the nearest station to their company $k+0.5$ years from now?
Constraints
・$2 \le N \le 3000$
・$1 \le M \le 5 \times 10^5$
・$1 \le u_i < v_i \le N$
・$1 \le s_j < t_j \le N$
・At present, it is possible to travel from any station to any station via some tracks.
・All inputs are integers.
Input
The input is given from standard input in the following format.$N\ M$
$u_1\ v_1$
$u_2\ v_2$
$u_3\ v_3$
$\vdots$
$u_{N-1}\ v_{N-1}$
$s_1\ t_1$
$s_2\ t_2$
$s_3\ t_3$
$\vdots$
$s_M\ t_M$
Output
Print $N-1$ lines. On the $k (1 \le k \le N-1)$-th line, print the number of office workers who can commute by Railway Y from the nearest station to their home to the nearest station to their company $k+0.5$ years from now.
Sample
Sample 1
Input
3 2
1 2
1 3
1 3
2 3
Output
1
0
After $1+0.5$ years, only track $1$ is unusable. At this time, office worker $1$ can commute from station $1$ to station $3$, but office worker $2$ cannot commute from station $2$ to station $3$.
Therefore, print $1$ on line $1$.
After $2+0.5$ years, track $1$ and track $2$ are unusable. At this time, neither office worker $1$ nor office worker $2$ can commute.
Therefore, print $0$ on line $2$.
Sample 2
Input
2 3
1 2
1 2
1 2
1 2
Output
0
There may be office workers who commute along the same route.
Sample 3
Input
10 4 2 3 2 6 1 8 1 4 6 10 5 6 1 9 1 6 7 9 1 4 4 6 1 5 2 5
Output
4 3 3 1 1 0 0 0 0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。