В Бертауне наступили тяжелые времена. В городе слишком много дорог, и их содержание дорого обходится правительству. В Бертауне n перекрестков и m двусторонних дорог, причем от каждого перекрестка можно добраться до любого другого. Мэр хочет закрыть некоторые дороги так, чтобы всего осталось n - 1 дорога, и по-прежнему от каждого перекрестка можно было добраться до любого другого. Кроме этого, мэра заботит количество тупиков — таких перекрестков, из которых выходит всего одна дорога. Тупиков должно быть не слишком много, но и не слишком мало. Мэр и его помощники посовещались и решили, что после закрытия в карте дорог должно быть ровно k тупиков. Ваша задача — посчитать количество различных способов закрытия дорог, при которых:
- Остается ровно n - 1 дорог.
- От каждого перекрестка можно добраться до любого другого.
- На получившейся карте ровно k тупиков.
Два способа считаются различными, если существует дорога, которая закрыта в первом способе и открыта во втором.
Выходные данные
Выведите одно число — искомое число способов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 2
1 2
2 3
1 3
|
3
|
|
2
|
4 6 2
1 2
2 3
3 4
4 1
1 3
2 4
|
12
|
|
3
|
4 6 3
1 2
2 3
3 4
4 1
1 3
2 4
|
4
|