该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

趁着最近放假，徐老师想出去旅游一次，徐老师今天来到了一个著名旅游城市

这个城市一共有 $n$ 个旅游景点，旅游景点之间一共有 $n-1$ 条道路，保证从任意一个景点出发可以到达任意其他景点，且景点之间的道路长度均相同

其中，为了推动旅游经济发展，这个城市还规划了 $m$ 条旅游巴士路线

第 $i$ 条旅游巴士会往返于 $x_i, y_i$ 两个景点之间（即从 $x_i$ 出发，沿着最近的路线到达 $y_i$，然后继续从 $y_i$ 出发回到 $x_i$，如此往复）

但是为了防止管理出现混乱，旅游巴士只允许在转折点处上车（也就是 $x_i,y_i$），中途每经过一个景点，车上的游客可以选择是否下车，但是中途不允许上车

现在徐老师正处于城市最著名的旅游景点 $1$ 处，他想知道对于任意一个景点，他最少需要换乘几次旅游巴士才能到达？

P.S. 由于徐老师很懒，他只会坐旅游巴士，不会自己以其他方式在景点之间移动

输入格式

输入第一行包含两个整数 $n,m$，表示这个城市有 $n$ 个旅游景点，$m$ 条旅游巴士路线

接下来 $n-1$ 行分别表示 $n-1$ 条道路，每行包含两个整数 $u_i,v_i$ 表示在 $u_v$ 和 $v_i$ 之间存在一条道路连接两个景点

接下来 $m$ 行，每行包含两个整数 $x_i,y_i$ 描述一条旅游巴士路线

输出格式

输出一行包含 $n - 1$ 个整数，依次表示徐老师从 $1$ 号景点出发分别到达 $2 \sim n$ 号景点需要的最少换乘次数，若无法到达则输出 $-1$

数据范围

对于 $30\%$ 的数据，满足 $n,m \leq 100$。

对于 $50\%$ 的数据，满足 $n,m \leq 30000$。

对于另外 $20\%$ 的数据，对于满足 $1 \leq i \leq n - 1$ 范围内的第 $i$ 个景点和 $i+1$ 个景点之间都存在一条道路

对于 $100\%$ 的数据，满足 $1 \leq n,m \leq 2 * 10^5$。

样例输入

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

样例输出

2 2 1 −1 3 3 −1 2 −1