Coke Robot Action Plans

On the planet Galidun, people love drinking Coke. In response, their hostile rivals created a Coke robot and placed it in city $1$. The robot has three possible actions each second:

• Stay: Remain in the current city.
• Move: Travel to any adjacent city (each neighboring city is a valid choice).
• Self-destruct: Explode and become permanently destroyed.

Once the robot self-destructs, it stops taking any actions and remains destroyed for all remaining seconds. At time $0$, the robot is active in city $1$. Given an undirected graph representing the cities of Galidun and an integer $t$, count the number of distinct behavior plans that can be observed over exactly $t$ seconds. A behavior plan is defined as the sequence of actions taken by the robot. Note that if the robot self-destructs at some second, then for all subsequent seconds there is no choice (the state remains destroyed).

Input Format:

The first line contains three integers $n$, $m$, and $t$, where

• $n$ is the number of cities.
• $m$ is the number of bidirectional roads.
• $t$ is the total number of seconds to simulate.

Each of the next $m$ lines contains two integers $u$ and $v$, indicating that there is a road connecting cities $u$ and $v$.

Output Format:

Output a single integer — the total number of distinct behavior plans possible after $t$ seconds.

Note: For an active robot, at each second:

• If the robot chooses Stay, it remains in the same city (1 possibility).
• If it chooses Move, then for a city with $d$ neighbors there are $d$ possibilities.
• If it chooses Self-destruct, the robot becomes destroyed (1 possibility) and no further actions occur in subsequent seconds (only 1 possibility in each remaining second).

You may assume that the input values are such that the answer fits in standard integer types.

inputFormat

The first line contains three space-separated integers $n$, $m$, and $t$.

Each of the next $m$ lines contains two space-separated integers $u$ and $v$, representing a bidirectional road between cities $u$ and $v$.

Example:

3 2 1
1 2
2 3

outputFormat

Output a single integer: the number of possible behavior plans after $t$ seconds.

Example:

3

sample

3 2 1
1 2
2 3

3

</p>