3483 - Frustrated Engineers

Created by Luis Manuel Díaz Barón & Frank Arteaga Salgado
Added by luismo (2015-12-05)
Limits
Total Time: 4000 MS | Test Time: 2000 MS |Memory: 512 MB | Output: 64 MB | Size: 9 KB
Enabled languages
Available in

Description

Some frustrated engineers from a frustrated network operator company asked you to solve the following problem: Given a tree of N (1 <= N <= 25) nodes. Can you find how many ways we can remove K nodes from it such that the remaining graph is still a tree?

A tree is a graph of one or more nodes such that there is exactly one single path between any two nodes. A path is a sequence of nodes V1, V2,...,Vm, such that for every i (1 <= i < m) there is an edge between node Vi and node Vi+1.
Some frustrated engineers from a frustrated network operator company asked you to solve the following problem: Given a tree of N (1 <= N <= 25) nodes. Can you find how many ways we can remove K nodes from it such that the remaining graph is still a tree?

A tree is a graph of one or more nodes such that there is exactly one single path between any two nodes. A path is a sequence of nodes V1, V2,...,Vm, such that for every i (1 <= i < m) there is an edge between node Vi and node Vi+1.
Some frustrated engineers from a frustrated network operator company asked you to solve the following problem: Given a tree of N (1 <= N <= 25) nodes. Can you find how many ways we can remove K nodes from it such that the remaining graph is still a tree?

A tree is a graph of one or more nodes such that there is exactly one single path between any two nodes. A path is a sequence of nodes V1, V2,...,Vm, such that for every i (1 <= i < m) there is an edge between node Vi and node Vi+1.

Input specification

The first line contains two space separated integers N (1 <= N <= 25) and K (1 <= K <= N). Th next N - 1 lines contain two space separated integers A and B meaning that there is an edge between node A and node B.
The first line contains two space separated integers N (1 <= N <= 25) and K (1 <= K <= N). Th next N - 1 lines contain two space separated integers A and B meaning that there is an edge between node A and node B.
The first line contains two space separated integers N (1 <= N <= 25) and K (1 <= K <= N). Th next N - 1 lines contain two space separated integers A and B meaning that there is an edge between node A and node B.

Output specification

Print a single integer containing the asked value.
Print a single integer containing the asked value.
The first line contains two space separated integers N (1 <= N <= 25) and K (1 <= K <= N). Th next N - 1 lines contain two space separated integers A and B meaning that there is an edge between node A and node B.

Sample input

9 2
2 3
2 1
9 8
5 9
6 5
4 1
5 7
1 5

Sample output

12

Hint(s)