[CQOI2017]小Q的棋盘

题目描述

小 Q 正在设计一种棋类游戏。 在小 Q 设计的游戏中,棋子可以放在棋盘上的格点中。某些格点之间有连线,棋子只能在有连线的格点之间移动。整个棋盘上共有 V 个格点,编号为0,1,2 … , 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 → 1 → 3 → 5 → 3 → 7,经过 0, 1, 3, 5, 7 这 5 个格点。 【数据规模与约定】 对于 100%的测试点,N,V ≤ 100, 0 ≤a\_i,b\_i< V