E. Тупики
ограничение по времени на тест
5 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

В Бертауне наступили тяжелые времена. В городе слишком много дорог, и их содержание дорого обходится правительству. В Бертауне n перекрестков и m двусторонних дорог, причем от каждого перекрестка можно добраться до любого другого. Мэр хочет закрыть некоторые дороги так, чтобы всего осталось n - 1 дорога, и по-прежнему от каждого перекрестка можно было добраться до любого другого. Кроме этого, мэра заботит количество тупиков — таких перекрестков, из которых выходит всего одна дорога. Тупиков должно быть не слишком много, но и не слишком мало. Мэр и его помощники посовещались и решили, что после закрытия в карте дорог должно быть ровно k тупиков. Ваша задача — посчитать количество различных способов закрытия дорог, при которых:

  • Остается ровно n - 1 дорог.
  • От каждого перекрестка можно добраться до любого другого.
  • На получившейся карте ровно k тупиков.

Два способа считаются различными, если существует дорога, которая закрыта в первом способе и открыта во втором.

Входные данные

В первой строке записано три целых числа n, m и k (3 ≤ n ≤ 10, n - 1 ≤ m ≤ n·(n - 1) / 2, 2 ≤ k ≤ n - 1) — количество перекрестков, дорог и тупиков соответственно. Далее следует m строк по два различных целых числа в каждой v1 и v2 (1 ≤ v1, v2 ≤ n, v1 ≠ v2) — номера перекрестков, которые соединяет очередная дорога. Между каждой парой перекрестков может быть не более одной дороги. Перекрестки нумеруются целыми числами от 1 до n. Гарантируется, что по исходным дорогам от каждого перекрестка можно добраться до любого другого.

Выходные данные

Выведите одно число — искомое число способов.

Примеры
Входные данные
3 3 2
1 2
2 3
1 3
Выходные данные
3
Входные данные
4 6 2
1 2
2 3
3 4
4 1
1 3
2 4
Выходные данные
12
Входные данные
4 6 3
1 2
2 3
3 4
4 1
1 3
2 4
Выходные данные
4