#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int inf = 1000000007;
const long long linf = 1LL << 62;
const unsigned long long ulinf = 1ULL << 63;
const double eps = 0.000001;
const double pi = 3.14159265358979323846;
template <class T>
T abs(T a) {
  return a >= 0 ? a : -a;
}
template <class T>
T sqr(T a) {
  return a * a;
}
template <class T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <class T>
T mod(T a, T b) {
  return (a % b + b) % b;
}
template <class T>
T lowbit(T x) {
  return x & -x;
}
long long powmod(long long a, long long b, long long c) {
  if (b == 0LL) return 1LL;
  long long ret = powmod(a, b >> 1, c);
  ret = ret * ret % c;
  if (b & 1LL) ret = ret * a % c;
  return ret;
}
long long modinv(long long a, long long b) { return powmod(a, b - 2LL, b); }
template <class T>
void maxe(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
void mine(T &a, T b) {
  if (a > b) a = b;
}
int iszero(double a) { return abs(a) <= eps; }
template <class T>
void geti(T &a) {
  a = 0;
  T b = 1;
  char c = getchar();
  if (c == '-')
    b = -1;
  else
    a = c - 48;
  while ((c = getchar()) != ' ' && c != '\n') a = a * 10 + c - 48;
  a *= b;
}
void fileio_in_out() {
  freopen(".in", "r", stdin);
  freopen(".out", "w", stdout);
}
void fileio_txt() {
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
}
const int N = 222222;
const int M = 22;
const int K = 22;
int test;
int n, m, k, ans;
int ord[N], id[N];
set<int> s;
vector<int> v[N];
int dep[N];
int anc[N][M];
void dfs(int fa, int cur, int depth) {
  id[ord[cur] = ++k] = cur;
  dep[cur] = depth;
  anc[cur][0] = fa;
  for (int i = 1; i < M; i++) anc[cur][i] = anc[anc[cur][i - 1]][i - 1];
  for (int i = 0, sz = v[cur].size(); i < sz; i++) {
    int next = v[cur][i];
    if (next != fa) dfs(cur, next, depth + 1);
  }
}
int lca(int x, int y) {
  if (dep[x] > dep[y]) swap(x, y);
  if (dep[x] < dep[y]) {
    int t = dep[y] - dep[x];
    for (int i = 0; i < M; i++)
      if (t & (1 << i)) y = anc[y][i];
  }
  if (x != y) {
    for (int i = M - 1; i >= 0; i--)
      if (anc[x][i] != anc[y][i]) {
        x = anc[x][i];
        y = anc[y][i];
      }
    x = anc[x][0];
    y = anc[y][0];
  }
  return x;
}
void init() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) v[i].clear();
  for (int i = 1; i < n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    v[x].push_back(y);
    v[y].push_back(x);
  }
  dfs(1, 1, 1);
}
int dist(int x, int y) {
  int t = lca(x, y);
  return dep[x] - dep[t] + dep[y] - dep[t];
}
int toadd(int x) {
  if (s.empty()) return 0;
  int ret;
  int mi = *s.begin(), ma = *s.rbegin();
  if (ord[x] < mi || ord[x] > ma) {
    ret = dist(x, id[mi]) + dist(x, id[ma]) - dist(id[mi], id[ma]);
  } else {
    set<int>::iterator nit = s.upper_bound(ord[x]), pit = nit;
    pit--;
    int prev = *pit, next = *nit;
    ret = dist(x, id[prev]) + dist(x, id[next]) - dist(id[prev], id[next]);
  }
  ret >>= 1;
  return ret;
}
int tosub(int x) {
  if (s.size() == 1) return 0;
  int ret;
  int mi = *s.begin(), ma = *s.rbegin();
  set<int>::iterator it = s.find(ord[x]);
  if (ord[x] == mi) {
    set<int>::iterator nit = it;
    nit++;
    int next = *nit;
    ret = dist(x, id[next]) + dist(x, id[ma]) - dist(id[next], id[ma]);
  } else if (ord[x] == ma) {
    set<int>::iterator pit = it;
    pit--;
    int prev = *pit;
    ret = dist(x, id[prev]) + dist(x, id[mi]) - dist(id[prev], id[mi]);
  } else {
    set<int>::iterator nit = it, pit = it;
    nit++;
    pit--;
    int prev = *pit, next = *nit;
    ret = dist(x, id[prev]) + dist(x, id[next]) - dist(id[prev], id[next]);
  }
  ret >>= 1;
  return ret;
}
void work() {
  int tot = 0;
  for (int i = 1, j = 1; i <= n; i++) {
    int t;
    while (j <= n && tot + (t = toadd(j)) < m) {
      tot += t;
      s.insert(ord[j++]);
    }
    maxe(ans, j - i);
    t = tosub(i);
    tot -= t;
    s.erase(ord[i]);
  }
  printf("%d\n", ans);
}
int main() {
  init();
  work();
  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

There is a tree consisting of n vertices. The vertices are numbered from 1 to n.

Let's define the length of an interval [l, r] as the value r - l + 1. The score of a subtree of this tree is the maximum length of such an interval [l, r] that, the vertices with numbers l, l + 1, ..., r belong to the subtree.

Considering all subtrees of the tree whose size is at most k, return the maximum score of the subtree. Note, that in this problem tree is not rooted, so a subtree — is an arbitrary connected subgraph of the tree.

Input

There are two integers in the first line, n and k (1 ≤ k ≤ n ≤ 105). Each of the next n - 1 lines contains integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi). That means ai and bi are connected by a tree edge.

It is guaranteed that the input represents a tree.

Output

Output should contain a single integer — the maximum possible score.

Examples

Input

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


Output

3


Input

16 7
13 11
12 11
2 14
8 6
9 15
16 11
5 14
6 15
4 3
11 15
15 14
10 1
3 14
14 7
1 7


Output

6

Note

For the first case, there is some subtree whose size is at most 6, including 3 consecutive numbers of vertices. For example, the subtree that consists of {1, 3, 4, 5, 7, 8} or of {1, 4, 6, 7, 8, 10} includes 3 consecutive numbers of vertices. But there is no subtree whose size is at most 6, which includes 4 or more consecutive numbers of vertices.

### Response

```cpp
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int inf = 1000000007;
const long long linf = 1LL << 62;
const unsigned long long ulinf = 1ULL << 63;
const double eps = 0.000001;
const double pi = 3.14159265358979323846;
template <class T>
T abs(T a) {
  return a >= 0 ? a : -a;
}
template <class T>
T sqr(T a) {
  return a * a;
}
template <class T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <class T>
T mod(T a, T b) {
  return (a % b + b) % b;
}
template <class T>
T lowbit(T x) {
  return x & -x;
}
long long powmod(long long a, long long b, long long c) {
  if (b == 0LL) return 1LL;
  long long ret = powmod(a, b >> 1, c);
  ret = ret * ret % c;
  if (b & 1LL) ret = ret * a % c;
  return ret;
}
long long modinv(long long a, long long b) { return powmod(a, b - 2LL, b); }
template <class T>
void maxe(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
void mine(T &a, T b) {
  if (a > b) a = b;
}
int iszero(double a) { return abs(a) <= eps; }
template <class T>
void geti(T &a) {
  a = 0;
  T b = 1;
  char c = getchar();
  if (c == '-')
    b = -1;
  else
    a = c - 48;
  while ((c = getchar()) != ' ' && c != '\n') a = a * 10 + c - 48;
  a *= b;
}
void fileio_in_out() {
  freopen(".in", "r", stdin);
  freopen(".out", "w", stdout);
}
void fileio_txt() {
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
}
const int N = 222222;
const int M = 22;
const int K = 22;
int test;
int n, m, k, ans;
int ord[N], id[N];
set<int> s;
vector<int> v[N];
int dep[N];
int anc[N][M];
void dfs(int fa, int cur, int depth) {
  id[ord[cur] = ++k] = cur;
  dep[cur] = depth;
  anc[cur][0] = fa;
  for (int i = 1; i < M; i++) anc[cur][i] = anc[anc[cur][i - 1]][i - 1];
  for (int i = 0, sz = v[cur].size(); i < sz; i++) {
    int next = v[cur][i];
    if (next != fa) dfs(cur, next, depth + 1);
  }
}
int lca(int x, int y) {
  if (dep[x] > dep[y]) swap(x, y);
  if (dep[x] < dep[y]) {
    int t = dep[y] - dep[x];
    for (int i = 0; i < M; i++)
      if (t & (1 << i)) y = anc[y][i];
  }
  if (x != y) {
    for (int i = M - 1; i >= 0; i--)
      if (anc[x][i] != anc[y][i]) {
        x = anc[x][i];
        y = anc[y][i];
      }
    x = anc[x][0];
    y = anc[y][0];
  }
  return x;
}
void init() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) v[i].clear();
  for (int i = 1; i < n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    v[x].push_back(y);
    v[y].push_back(x);
  }
  dfs(1, 1, 1);
}
int dist(int x, int y) {
  int t = lca(x, y);
  return dep[x] - dep[t] + dep[y] - dep[t];
}
int toadd(int x) {
  if (s.empty()) return 0;
  int ret;
  int mi = *s.begin(), ma = *s.rbegin();
  if (ord[x] < mi || ord[x] > ma) {
    ret = dist(x, id[mi]) + dist(x, id[ma]) - dist(id[mi], id[ma]);
  } else {
    set<int>::iterator nit = s.upper_bound(ord[x]), pit = nit;
    pit--;
    int prev = *pit, next = *nit;
    ret = dist(x, id[prev]) + dist(x, id[next]) - dist(id[prev], id[next]);
  }
  ret >>= 1;
  return ret;
}
int tosub(int x) {
  if (s.size() == 1) return 0;
  int ret;
  int mi = *s.begin(), ma = *s.rbegin();
  set<int>::iterator it = s.find(ord[x]);
  if (ord[x] == mi) {
    set<int>::iterator nit = it;
    nit++;
    int next = *nit;
    ret = dist(x, id[next]) + dist(x, id[ma]) - dist(id[next], id[ma]);
  } else if (ord[x] == ma) {
    set<int>::iterator pit = it;
    pit--;
    int prev = *pit;
    ret = dist(x, id[prev]) + dist(x, id[mi]) - dist(id[prev], id[mi]);
  } else {
    set<int>::iterator nit = it, pit = it;
    nit++;
    pit--;
    int prev = *pit, next = *nit;
    ret = dist(x, id[prev]) + dist(x, id[next]) - dist(id[prev], id[next]);
  }
  ret >>= 1;
  return ret;
}
void work() {
  int tot = 0;
  for (int i = 1, j = 1; i <= n; i++) {
    int t;
    while (j <= n && tot + (t = toadd(j)) < m) {
      tot += t;
      s.insert(ord[j++]);
    }
    maxe(ans, j - i);
    t = tosub(i);
    tot -= t;
    s.erase(ord[i]);
  }
  printf("%d\n", ans);
}
int main() {
  init();
  work();
  return 0;
}

```