A tree is an undirected connected graph without cycles. The distance between two vertices is the number of edges in a simple path between them.

Limak is a little polar bear. He lives in a tree that consists of n vertices, numbered 1 through n.

Limak recently learned how to jump. He can jump from a vertex to any vertex within distance at most k.

For a pair of vertices (s, t) we define f(s, t) as the minimum number of jumps Limak needs to get from s to t. Your task is to find the sum of f(s, t) over all pairs of vertices (s, t) such that s < t.

Input

The first line of the input contains two integers n and k (2 ≤ n ≤ 200 000, 1 ≤ k ≤ 5) — the number of vertices in the tree and the maximum allowed jump distance respectively.

The next n - 1 lines describe edges in the tree. The i-th of those lines contains two integers ai and bi (1 ≤ ai, bi ≤ n) — the indices on vertices connected with i-th edge.

It's guaranteed that the given edges form a tree.

Output

Print one integer, denoting the sum of f(s, t) over all pairs of vertices (s, t) such that s < t.

Examples

Input

6 2
1 2
1 3
2 4
2 5
4 6


Output

20


Input

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


Output

114


Input

3 5
2 1
3 1


Output

3

Note

In the first sample, the given tree has 6 vertices and it's displayed on the drawing below. Limak can jump to any vertex within distance at most 2. For example, from the vertex 5 he can jump to any of vertices: 1, 2 and 4 (well, he can also jump to the vertex 5 itself).

<image>

There are <image> pairs of vertices (s, t) such that s < t. For 5 of those pairs Limak would need two jumps: (1, 6), (3, 4), (3, 5), (3, 6), (5, 6). For other 10 pairs one jump is enough. So, the answer is 5·2 + 10·1 = 20.

In the third sample, Limak can jump between every two vertices directly. There are 3 pairs of vertices (s < t), so the answer is 3·1 = 3.
#include <bits/stdc++.h>
using namespace std;
long long r, m, a[500005], n, b[500005], c[500005];
vector<long long> v[500005];
struct rd {
  long long e[5] = {0};
};
vector<rd> remainds[500005];
rd dfs(long long x, long long dis) {
  long long i, j, k;
  a[x] = 1;
  rd temp, fi;
  for (i = 0; i < v[x].size(); i++) {
    if (a[v[x][i]] == 1) continue;
    temp = dfs(v[x][i], dis + 1);
    remainds[x].push_back(temp);
    for (j = 0; j < r; j++) fi.e[(j + 1) % r] += temp.e[j];
  }
  fi.e[1ll % r]++;
  m = m + dis / r + (dis % r != 0);
  return fi;
}
void dfg(long long x, rd pre, long long ans) {
  long long i, j, k, l;
  rd tot;
  b[x] = 1;
  for (i = 0; i < r; i++) tot.e[(i + 1) % r] = pre.e[i];
  ans = ans + tot.e[1];
  rd n1, te, pt;
  for (i = 0; i < remainds[x].size(); i++) {
    for (j = 0; j < r; j++) te.e[j] += remainds[x][i].e[j];
  }
  ans -= te.e[0];
  tot.e[1]++;
  for (j = 0; j < r; j++) tot.e[j] += te.e[j];
  l = 0;
  m = m + ans;
  for (i = 0; i < v[x].size(); i++) {
    if (b[v[x][i]] == 1) continue;
    rd ft;
    for (j = 0; j < r; j++) ft.e[j] = tot.e[j] - remainds[x][l].e[j];
    l++;
    dfg(v[x][i], ft, ans);
  }
}
long long dft(long long x) {
  long long i, j, k = 1;
  c[x] = 1;
  rd temp, fi;
  for (i = 0; i < v[x].size(); i++) {
    if (c[v[x][i]] == 1) continue;
    k += dft(v[x][i]);
  }
  m = m + k * (n - k);
  return k;
}
int main() {
  ios_base::sync_with_stdio(0);
  long long k = 0, t = 0, x, sum = 0, q, y = 0, l = 0, i, j, z, p;
  cin >> n >> r;
  for (i = 0; i < n - 1; i++) {
    cin >> x >> y;
    v[x].push_back(y);
    v[y].push_back(x);
  }
  a[1] = 1;
  rd n1, gurz, temp;
  for (i = 0; i < v[1].size(); i++) {
    n1 = dfs(v[1][i], 1);
    remainds[1].push_back(n1);
    for (j = 0; j < r; j++) gurz.e[j] += n1.e[j];
  }
  x = m;
  b[1] = 1;
  for (i = 0; i < v[1].size(); i++) {
    n1 = remainds[1][i];
    for (j = 0; j < r; j++) temp.e[j] = gurz.e[j] - n1.e[j];
    dfg(v[1][i], temp, x);
  }
  if (r > 1)
    cout << m / 2;
  else {
    m = 0;
    c[1] = 1;
    dft(1);
    cout << m;
  }
  return 0;
}
