Counting Vertices in Iterated Line Graphs of a Tree

Given a tree T with n nodes and n-1 edges, we define the line graph transformation as follows: the line graph of an undirected graph G = (V, E) is an undirected graph L(G) whose vertices correspond one‐to‐one with the edges in G. Two vertices in L(G) are adjacent if and only if their corresponding edges in G share a common endpoint. In other words, for every vertex v in G with degree d(v), the edges incident on v form a clique of size d(v) in L(G).

We denote by \(L^k(T)\) the graph obtained after applying the line graph transformation k times on T (with \(L^0(T) = T\)). Notice that for any graph \(G\), the number of vertices in \(L(G)\) is \(|E(G)|\).

Your task is to compute the number of vertices in \(L^k(T)\). For example, when k = 0, the answer is simply n; when k \ge 1, the answer is the number of edges in \(L^{k-1}(T)\>.

Note: Due to the nature of the transformation, even a simple tree can yield a complicated graph after several iterations. You only need to output the number of vertices in \(L^k(T)\), which is guaranteed to fit within the limits of standard 64-bit integer arithmetic for the given input constraints.

Mathematical formulation:

Let T be a tree with n vertices and n-1 edges. Then, defining \(a_0 = n\) and for \(k \ge 1\), \(a_k = |E(L^{k-1}(T))|,\) the task is to compute \(a_k\).

inputFormat

The first line contains two integers n and k (with n ≥ 1), where n is the number of nodes in the tree T and k is the number of times to apply the line graph transformation. The next n-1 lines each contain two integers u and v (1-based indices) indicating an edge between nodes u and v in the tree.

outputFormat

Output a single integer: the number of vertices in \(L^k(T)\).

sample

4 1
1 2
2 3
3 4

3