# #715. 【北大集训2021】小明的树

$n-1$ 次点灯后计数器的值，记为这棵树的答案。

### 样例一

#### input

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



#### output

13
15
4
6
2
2
10
7
8
8
7



### 样例二

#### input

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



#### output

3
2
2
1
2
4
4
3
3
3
3



### 数据范围与提示

• 子任务$1$（$10$ 分）：保证满足 $2 \leq n \leq 500000$，$m = 0$。

• 子任务$2$（$20$ 分）：保证满足 $2 \leq n \leq 8000$，$0 \leq m \leq 8000$。

• 子任务$3$（$70$ 分）：保证满足 $2 \leq n \leq 500000$，$0\leq m \leq 500000$。