#include <bits/stdc++.h>
using namespace std;
const int MAXN = (1 << 20);
const int MAXLOG = 24;
struct node {
  int sum, lazy;
  node() {
    sum = 0;
    lazy = 0;
  }
  node(int val) {
    sum = val;
    lazy = 0;
  }
};
node temp, broken;
node merge(node l, node r) {
  temp.sum = l.sum + r.sum;
  temp.lazy = 0;
  return temp;
}
struct segment_tree {
  node tr[4 * MAXN];
  void update(int l, int r, int idx) {
    if (tr[idx].lazy) {
      tr[idx].sum += (r - l + 1) * tr[idx].lazy;
      if (l != r) {
        tr[2 * idx + 1].lazy += tr[idx].lazy;
        tr[2 * idx + 2].lazy += tr[idx].lazy;
      }
      tr[idx].lazy = 0;
    }
  }
  void init(int l, int r, int idx) {
    if (l == r) {
      tr[idx] = node(0);
      return;
    }
    int mid = (l + r) >> 1;
    init(l, mid, 2 * idx + 1);
    init(mid + 1, r, 2 * idx + 2);
    tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
  }
  void update(int qL, int qR, int val, int l, int r, int idx) {
    update(l, r, idx);
    if (qL > r || l > qR) return;
    if (qL <= l && r <= qR) {
      tr[idx].lazy += val;
      update(l, r, idx);
      return;
    }
    int mid = (l + r) >> 1;
    update(qL, qR, val, l, mid, 2 * idx + 1);
    update(qL, qR, val, mid + 1, r, 2 * idx + 2);
    tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
  }
  node query(int qL, int qR, int l, int r, int idx) {
    update(l, r, idx);
    if (l > qR || r < qL) return broken;
    if (qL <= l && r <= qR) return tr[idx];
    int mid = (l + r) >> 1;
    return merge(query(qL, qR, l, mid, 2 * idx + 1),
                 query(qL, qR, mid + 1, r, 2 * idx + 2));
  }
};
int n, k;
vector<int> G[MAXN];
void read() {
  cin >> n >> k;
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
}
int lgn, st[MAXN], en[MAXN], dfs_time = 0;
int par[MAXN][MAXLOG], root = 1;
int di[MAXN];
void dfs(int u) {
  int sz = G[u].size(), v;
  st[u] = ++dfs_time;
  for (int i = 1; i <= lgn; i++) par[u][i] = par[par[u][i - 1]][i - 1];
  for (int i = 0; i < sz; i++) {
    v = G[u][i];
    if (v != par[u][0]) {
      par[v][0] = u;
      di[v] = di[u] + 1;
      dfs(v);
    }
  }
  en[u] = dfs_time;
}
inline bool upper(int u, int v) { return st[u] <= st[v] && en[v] <= en[u]; }
int lca(int u, int v) {
  if (upper(u, v)) return u;
  if (upper(v, u)) return v;
  int a = u;
  for (int i = lgn; i >= 0; i--)
    if (!upper(par[a][i], v)) a = par[a][i];
  return par[a][0];
}
int parent(int u, int up) {
  int a = u;
  for (int i = lgn; i >= 0; i--)
    if (up & (1 << i)) a = par[a][i];
  return a;
}
void lca_precompute(int _root) {
  root = _root;
  lgn = 0;
  while ((1 << lgn) <= n) lgn++;
  for (int i = 0; i <= lgn; i++) par[root][i] = root;
  di[root] = 0;
  dfs_time = 0;
  dfs(root);
}
struct segment_tree_lca {
  int tr[4 * MAXN];
  void init(int l, int r, int idx) {
    if (l == r) {
      tr[idx] = l;
      return;
    }
    int mid = (l + r) >> 1;
    init(l, mid, 2 * idx + 1);
    init(mid + 1, r, 2 * idx + 2);
    tr[idx] = lca(tr[2 * idx + 1], tr[2 * idx + 2]);
  }
  int query(int qL, int qR, int l, int r, int idx) {
    if (l > qR || r < qL) return -1;
    if (qL <= l && r <= qR) return tr[idx];
    int mid = (l + r) >> 1;
    int l1 = query(qL, qR, l, mid, 2 * idx + 1);
    int l2 = query(qL, qR, mid + 1, r, 2 * idx + 2);
    if (l1 == -1) return l2;
    if (l2 == -1) return l1;
    return lca(l1, l2);
  }
};
segment_tree t;
segment_tree_lca tl;
int ans = 0, curr_sz = 0, l = 1, r = 0, last_lca;
void add(int pos) {
  if (t.query(1, dfs_time, 1, dfs_time, 0).sum == 0) {
    curr_sz++;
    t.update(st[pos], st[pos], 1, 1, dfs_time, 0);
    last_lca = pos;
    return;
  }
  if (t.query(st[pos], en[pos], 1, dfs_time, 0).sum) {
    t.update(st[pos], st[pos], 1, 1, dfs_time, 0);
    curr_sz += di[last_lca] - di[tl.query(l, r, 1, n, 0)];
    last_lca = tl.query(l, r, 1, n, 0);
    return;
  }
  int u = pos;
  for (int lg = lgn; lg >= 0; lg--)
    if (t.query(st[par[u][lg]], en[par[u][lg]], 1, dfs_time, 0).sum == 0)
      u = par[u][lg];
  u = par[u][0];
  curr_sz += di[pos] - di[u];
  t.update(st[pos], st[pos], 1, 1, dfs_time, 0);
  curr_sz += di[last_lca] - di[tl.query(l, r, 1, n, 0)];
  last_lca = tl.query(l, r, 1, n, 0);
}
void del(int pos) {
  t.update(st[pos], st[pos], -1, 1, dfs_time, 0);
  if (t.query(st[pos], en[pos], 1, dfs_time, 0).sum) {
    curr_sz -= di[tl.query(l, r, 1, n, 0)] - di[last_lca];
    last_lca = tl.query(l, r, 1, n, 0);
    return;
  }
  int u = pos;
  for (int lg = lgn; lg >= 0; lg--)
    if (t.query(st[par[u][lg]], en[par[u][lg]], 1, dfs_time, 0).sum == 0)
      u = par[u][lg];
  u = par[u][0];
  curr_sz -= di[pos] - di[u];
  curr_sz -= di[tl.query(l, r, 1, n, 0)] - di[last_lca];
  last_lca = tl.query(l, r, 1, n, 0);
}
void solve() {
  lca_precompute(1);
  t.init(1, dfs_time, 0);
  tl.init(1, n, 0);
  while (r < n) {
    add(++r);
    while (curr_sz > k) del(l++);
    ans = max(ans, r - l + 1);
  }
  cout << ans << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  read();
  solve();
  return 0;
}

### Prompt

In cpp, your task is to solve the following problem:

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>
using namespace std;
const int MAXN = (1 << 20);
const int MAXLOG = 24;
struct node {
  int sum, lazy;
  node() {
    sum = 0;
    lazy = 0;
  }
  node(int val) {
    sum = val;
    lazy = 0;
  }
};
node temp, broken;
node merge(node l, node r) {
  temp.sum = l.sum + r.sum;
  temp.lazy = 0;
  return temp;
}
struct segment_tree {
  node tr[4 * MAXN];
  void update(int l, int r, int idx) {
    if (tr[idx].lazy) {
      tr[idx].sum += (r - l + 1) * tr[idx].lazy;
      if (l != r) {
        tr[2 * idx + 1].lazy += tr[idx].lazy;
        tr[2 * idx + 2].lazy += tr[idx].lazy;
      }
      tr[idx].lazy = 0;
    }
  }
  void init(int l, int r, int idx) {
    if (l == r) {
      tr[idx] = node(0);
      return;
    }
    int mid = (l + r) >> 1;
    init(l, mid, 2 * idx + 1);
    init(mid + 1, r, 2 * idx + 2);
    tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
  }
  void update(int qL, int qR, int val, int l, int r, int idx) {
    update(l, r, idx);
    if (qL > r || l > qR) return;
    if (qL <= l && r <= qR) {
      tr[idx].lazy += val;
      update(l, r, idx);
      return;
    }
    int mid = (l + r) >> 1;
    update(qL, qR, val, l, mid, 2 * idx + 1);
    update(qL, qR, val, mid + 1, r, 2 * idx + 2);
    tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
  }
  node query(int qL, int qR, int l, int r, int idx) {
    update(l, r, idx);
    if (l > qR || r < qL) return broken;
    if (qL <= l && r <= qR) return tr[idx];
    int mid = (l + r) >> 1;
    return merge(query(qL, qR, l, mid, 2 * idx + 1),
                 query(qL, qR, mid + 1, r, 2 * idx + 2));
  }
};
int n, k;
vector<int> G[MAXN];
void read() {
  cin >> n >> k;
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
}
int lgn, st[MAXN], en[MAXN], dfs_time = 0;
int par[MAXN][MAXLOG], root = 1;
int di[MAXN];
void dfs(int u) {
  int sz = G[u].size(), v;
  st[u] = ++dfs_time;
  for (int i = 1; i <= lgn; i++) par[u][i] = par[par[u][i - 1]][i - 1];
  for (int i = 0; i < sz; i++) {
    v = G[u][i];
    if (v != par[u][0]) {
      par[v][0] = u;
      di[v] = di[u] + 1;
      dfs(v);
    }
  }
  en[u] = dfs_time;
}
inline bool upper(int u, int v) { return st[u] <= st[v] && en[v] <= en[u]; }
int lca(int u, int v) {
  if (upper(u, v)) return u;
  if (upper(v, u)) return v;
  int a = u;
  for (int i = lgn; i >= 0; i--)
    if (!upper(par[a][i], v)) a = par[a][i];
  return par[a][0];
}
int parent(int u, int up) {
  int a = u;
  for (int i = lgn; i >= 0; i--)
    if (up & (1 << i)) a = par[a][i];
  return a;
}
void lca_precompute(int _root) {
  root = _root;
  lgn = 0;
  while ((1 << lgn) <= n) lgn++;
  for (int i = 0; i <= lgn; i++) par[root][i] = root;
  di[root] = 0;
  dfs_time = 0;
  dfs(root);
}
struct segment_tree_lca {
  int tr[4 * MAXN];
  void init(int l, int r, int idx) {
    if (l == r) {
      tr[idx] = l;
      return;
    }
    int mid = (l + r) >> 1;
    init(l, mid, 2 * idx + 1);
    init(mid + 1, r, 2 * idx + 2);
    tr[idx] = lca(tr[2 * idx + 1], tr[2 * idx + 2]);
  }
  int query(int qL, int qR, int l, int r, int idx) {
    if (l > qR || r < qL) return -1;
    if (qL <= l && r <= qR) return tr[idx];
    int mid = (l + r) >> 1;
    int l1 = query(qL, qR, l, mid, 2 * idx + 1);
    int l2 = query(qL, qR, mid + 1, r, 2 * idx + 2);
    if (l1 == -1) return l2;
    if (l2 == -1) return l1;
    return lca(l1, l2);
  }
};
segment_tree t;
segment_tree_lca tl;
int ans = 0, curr_sz = 0, l = 1, r = 0, last_lca;
void add(int pos) {
  if (t.query(1, dfs_time, 1, dfs_time, 0).sum == 0) {
    curr_sz++;
    t.update(st[pos], st[pos], 1, 1, dfs_time, 0);
    last_lca = pos;
    return;
  }
  if (t.query(st[pos], en[pos], 1, dfs_time, 0).sum) {
    t.update(st[pos], st[pos], 1, 1, dfs_time, 0);
    curr_sz += di[last_lca] - di[tl.query(l, r, 1, n, 0)];
    last_lca = tl.query(l, r, 1, n, 0);
    return;
  }
  int u = pos;
  for (int lg = lgn; lg >= 0; lg--)
    if (t.query(st[par[u][lg]], en[par[u][lg]], 1, dfs_time, 0).sum == 0)
      u = par[u][lg];
  u = par[u][0];
  curr_sz += di[pos] - di[u];
  t.update(st[pos], st[pos], 1, 1, dfs_time, 0);
  curr_sz += di[last_lca] - di[tl.query(l, r, 1, n, 0)];
  last_lca = tl.query(l, r, 1, n, 0);
}
void del(int pos) {
  t.update(st[pos], st[pos], -1, 1, dfs_time, 0);
  if (t.query(st[pos], en[pos], 1, dfs_time, 0).sum) {
    curr_sz -= di[tl.query(l, r, 1, n, 0)] - di[last_lca];
    last_lca = tl.query(l, r, 1, n, 0);
    return;
  }
  int u = pos;
  for (int lg = lgn; lg >= 0; lg--)
    if (t.query(st[par[u][lg]], en[par[u][lg]], 1, dfs_time, 0).sum == 0)
      u = par[u][lg];
  u = par[u][0];
  curr_sz -= di[pos] - di[u];
  curr_sz -= di[tl.query(l, r, 1, n, 0)] - di[last_lca];
  last_lca = tl.query(l, r, 1, n, 0);
}
void solve() {
  lca_precompute(1);
  t.init(1, dfs_time, 0);
  tl.init(1, n, 0);
  while (r < n) {
    add(++r);
    while (curr_sz > k) del(l++);
    ans = max(ans, r - l + 1);
  }
  cout << ans << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  read();
  solve();
  return 0;
}

```