题目描述

有一个国家共 $n$ 个城市，编号 $1$ ~ $n$ ，城市之间由 $n-1$ 条双向道路连接，任意城市之间均连通。

现有 $m$ 名游客前往该国家游玩，第 $i$ 名游客的旅游路线起点为 $s_i$ ，终点为 $t_i$ ，且沿途不会经过重复道路。已知每名游客在经过某一城市时都会打卡（包括起点城市和终点城市），请你帮忙求出每个城市被打卡的次数。

输入格式

输入第一行，两个正整数 $n,m$ 接下来 $n-1$ 行，每行两个正整数 $u_i,v_i$ ，表示第 $i$ 条道路连接城市 $u_i,v_i$ 最后 $m$ 行，每行两个正整数 $s_i,t_i$ ，表示第 $i$ 名游客旅游路线的起点和终点

输出格式

输出共一行， $n$个整数，其中第 $i$ 个整数表示 $i$ 号城市被打卡的数量

4 3
1 2
2 3
4 2
1 4
3 4
2 4

1 3 1 3

数据范围

• 对于$30\%$的数据，$1\leq n,m \leq 100$
• 对于$60\%$的数据，$1\leq n,m \leq 10^3$
• 对于$100\%$的数据，$1\leq n,m \leq 10^5$ , $1 \leq u_i,v_i,s_i,t_i \leq n$