Bob is making a journey on a tree with nodes and edges. The nodes are numbered from to , and there is exactly one simple path between any two nodes. Bob starts his journey from node . Each step, Bob can move from his current node to an adjacent node. If Bob travels on the same edge twice, it will take him two steps. Due to his busy schedule, Bob can only move up to steps. Your task is to find the maximum number of distinct nodes Bob can visit during his journey.
Input Specification
The first line contains two integers and (, ), representing the number of nodes in the tree and the maximum number of steps Bob can take, respectively.
Each of the next lines contains two integers and (, ), indicating an edge between nodes and .
Output Specification
Output a single integer representing the maximum number of distinct nodes Bob can visit.
Constraints
Subtask | Points | Additional constraints |
---|---|---|
, | ||
, | ||
No additional constraints |
Sample Input 1
5 2
2 1
3 2
4 3
5 4
Sample Output 1
3
Explanation
Bob can start from , move to , and finally stop at . He will visit nodes in total.
Sample Input 2
9 8
1 2
1 3
2 4
2 9
4 6
4 8
3 5
3 7
Sample Output 2
6
Comments