Edward has a tree with `n` vertices conveniently labeled with 1,2,…,`n`.

Edward finds a pair of paths on the tree which share no more than `k` common vertices. Now Edward is interested in the number of such ordered pairs of paths.

Note that path from vertex `a` to `b` is the same as the path from vertex `b` to `a`. An ordered pair means (`A`, `B`) is different from (`B`, `A`) unless `A` is equal to `B`.

There are multiple test cases. The first line of input contains an integer `T` indicating the number of test cases. For each test case:

The first line contains two integers `n`, `k` (1 ≤ `n`, `k` ≤ 88888). Each of the following `n` - 1 lines contains two integers `a`_{i}, `b`_{i}, denoting an edge between vertices `a`_{i} and `b`_{i} (1 ≤ `a`_{i}, `b`_{i} ≤ `n`).

The sum of values `n` for all the test cases does not exceed 888888.

For each case, output a single integer denoting the number of ordered pairs of paths sharing no more than `k` vertices.

The number of path pairs that shares no common vertex is 30.

The number of path pairs that shares 1 common vertex is 44.

The number of path pairs that shares 2 common vertices is 19.

path A |
paths share 2 vertices with A |
total |
---|---|---|

1-2-3-4 | 1-2, 2-3, 3-4 | 3 |

1-2-3 | 1-2, 2-3, 2-3-4 | 3 |

2-3-4 | 1-2-3, 2-3, 3-4 | 3 |

1-2 | 1-2, 1-2-3, 1-2-3-4 | 3 |

2-3 | 1-2-3, 1-2-3-4, 2-3, 2-3-4 | 4 |

3-4 | 1-2-3-4, 2-3-4, 3-4 | 3 |

提交代码