Watermelon Throwing Game

In a class of \(n\) children, they are not paying attention in class but are busy playing a watermelon throwing game on Facebook. The children are numbered from 1 to \(n\), and Goran is numbered 1. In the first lesson, Goran throws one watermelon to each of his friends. In every subsequent lesson, each child acts according to the number of watermelons they were hit with in the previous lesson:

• If a child was hit by an odd number of watermelons in the previous lesson, then in the current lesson he throws one watermelon to each of his friends.
• If a child was hit by an even number (including \(0\)) of watermelons in the previous lesson, then in the current lesson he throws two watermelons to each of his friends.

You are given the number of children \(n\), the number of bidirectional friendship relations \(m\), and the number of lessons \(h\). Then, for each friendship relation a pair of integers \(u\) and \(v\) is provided indicating that child \(u\) and child \(v\) are friends. Simulate the game and calculate the total number of watermelons thrown after \(h\) lessons.

inputFormat

The first line contains three integers \(n\), \(m\), and \(h\), representing the number of children, the number of friendship relations, and the number of lessons respectively. Each of the next \(m\) lines contains two integers \(u\) and \(v\), meaning that child \(u\) and child \(v\) are friends (the friendship relation is bidirectional).

outputFormat

Output a single integer, the total number of watermelons thrown by all the children after \(h\) lessons.

sample

3 2 1
1 2
2 3

1