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.
import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class C {
  static BufferedReader in = null;
  static PrintWriter out = null;
  static StringTokenizer st = new StringTokenizer("");

  public static void main(String[] args) {
    try {
      in = new BufferedReader(new InputStreamReader(System.in));
      out = new PrintWriter(System.out);
      solve();
      out.close();
      in.close();
    } catch (Exception e) {
      e.printStackTrace();
    }
  }

  public static String readString() {
    while (!st.hasMoreTokens()) {
      try {
        st = new StringTokenizer(in.readLine());
      } catch (Exception e) {
        e.printStackTrace();
      }
    }
    return st.nextToken();
  }


  public static int readInt() {
    return Integer.parseInt(readString());
  }

  public static long readLong() {
    return Long.parseLong(readString());
  }

  public static double readDouble() {
    return Double.parseDouble(readString());
  }


  static List<Integer>[] graph;
  static int[][] ost;
  static boolean[] used;
  static long ans = 0;
  static int k;
  static long[] sums;
  static int[][] ostRight;
  static long[] sumsRight;

  private static void solve() throws IOException {
    int n = readInt();
    k = readInt();
    sums = new long[n];
    sumsRight = new long[n];
    graph = new ArrayList[n];
    ost = new int[n][k];
    ostRight = new int[n][k];
    used = new boolean[n];
    for (int i = 0; i < n; i++) {
      graph[i] = new ArrayList<>();
    }
    for (int i = 0; i < n - 1; i++) {
      int from = readInt() - 1;
      int to = readInt() - 1;
      graph[from].add(to);
      graph[to].add(from);
    }
    for (int i = 0; i < n; i++) {
      if (graph[i].size() == 1) {
        dfs(i, i);
        break;
      }
    }
    out.print(ans);
  }

  private static void dfs(int from, int x) {
    used[x] = true;
    for (int i = 0; i < k; i++) {
      ost[x][(i + 1) % k] += ost[from][i] + ostRight[from][i];
    }
    long curAns = sums[from] + sumsRight[from];
    long temp = ostRight[from][0] == 0 ? 0 : ostRight[from][0] /*- 1*/;
    curAns += ost[from][0] + temp;
    ans += curAns;
    sums[x] = curAns;
    ost[x][0]++;

    //sums[x]++;

    for (int to : graph[x]) {
      if (!used[to]) {
        dfs(x, to);
      }
    }

    ostRight[x][0]++;
    for (int i = 0; i < k; i++) {
      ostRight[from][(i + 1) % k] += ostRight[x][i];
    }
    curAns = sumsRight[x];
    curAns += ostRight[x][0];
    sumsRight[from] += curAns;
  }


}