[CQOI2017] 小Q的棋盘

题目描述

小 Q 正在设计一种棋类游戏。 在小 Q 设计的游戏中,棋子可以放在棋盘上的格点中。某些格点之间有连线,棋子只能在有连线的格点之间移动。整个棋盘上共有 $V$ 个格点,编号为 $0,1,2,\cdots, V- 1$,它们是连通的,也就是说棋子从任意格点出发,总能到达所有的格点。小 Q 在设计棋盘时,还保证棋子从一个格点移动到另外任一格点的路径是唯一的。 小 Q 现在想知道,当棋子从格点 $0$ 出发,移动 $N$ 步最多能经过多少格点。格点可以重复经过多次,但不重复计数。

输入输出格式

输入格式


第一行包含2个正整数 $V, N$,其中 $V$ 表示格点总数,$N$ 表示移动步数。 接下来 $V-1$ 行,每行两个数 $a_i,b_i$,表示编号为$a_i,b_i$ 的两个格点之间有连线。

输出格式


输出一行一个整数,表示最多经过的格点数量。

输入输出样例

输入样例 #1

5 2
1 0
2 1
3 2
4 3

输出样例 #1

3

输入样例 #2

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

输出样例 #2

5

说明

【输入输出样例 1 说明】 从格点 $0$ 出发移动 $2$ 步。经过 $0, 1, 2$ 这 $3$ 个格点。 【输入输出样例 2 说明】 一种可行的移动路径为 $0 \to 1 \to 3 \to 5 \to 3 \to 7$,经过 $0, 1, 3, 5, 7$ 这 $5$ 个格点。 【数据规模与约定】 对于 $100\%$ 的测试点,$1\le N,V ≤ 100$,$0 ≤a_i,b_i< V$。