Legendary Journey

In a country with \(N\) cities, Alice dreams of embarking on a legendary journey. Alice intends to start at one city and travel by moving to an adjacent city at each step. The journey must visit exactly \(K\) cities, including both the starting city and the destination, with no city visited more than once. Two cities \(u\) and \(v\) can serve as a valid start and end if there exists a simple path (a path with no repeated vertices) from \(u\) to \(v\) that uses exactly \(K\) distinct cities.

You are given an undirected graph representing the cities and the roads between them. Determine the number of ordered pairs \((u, v)\) (with \(u \neq v\)) for which there exists a simple path containing exactly \(K\) cities.

Note: A path is defined as a sequence of cities where every consecutive pair is connected by a road, and all cities in the path are distinct.

inputFormat

The first line contains three integers \(N\), \(M\), and \(K\) --- the number of cities, the number of roads, and the exact number of cities to visit, respectively.

Each of the next \(M\) lines contains two integers \(u\) and \(v\), representing an undirected road between city \(u\) and city \(v\). Cities are numbered from 1 to \(N\).

outputFormat

Output a single integer representing the number of valid ordered pairs \((u, v)\) (with \(u \neq v\)) for which there exists a simple path that visits exactly \(K\) cities.

sample

3 2 2
1 2
2 3

4