The latest game produced by your company has just premiered. The subsequent adventures of a hero traversing the Galaxy – a wandering quasar slayer – are selling well and receiving quite good reviews. Some only complain that the game's mechanics are too complicated. It is a good thing they know nothing about what the production process was really like: sleepless nights, unhealthy eating, a tense atmosphere, and a random number generator that had to replace one of the key employees... it will definitely be better if all of this never comes to light.

During the game, the player's character can learn one of $n$ skills (such as piloting spaceships, elemental magic, or programming in PHP). The skills are connected by a dependency network: there are $m$ pairs $(x, y)$ such that skill $y$ can only be learned after learning skill $x$. There are no cycles in the dependency network, meaning there is no situation where one would need to know a skill to learn that same skill. Formally speaking, the skills form a directed acyclic graph (DAG).

Oh, did we mention the random number generator that had to replace the departing employee? It was the one that created the skill network. First, it assigned them numbers $1, 2, \dots, n$ in a random way, and then it drew $m$ distinct pairs $(x, y)$ such that $x < y$ and created dependencies between the skills from these pairs. This cut off endless discussions between programmers and significantly accelerated production, and also forced you to announce the generator as Employee of the Month.

The complexity degree of such a skill network is the length of the longest chain that can be found in it – in other words, the longest possible sequence such that each skill in it requires the previous one. A too-high complexity degree makes it difficult for players to find their way around the game's mechanics, and additionally, the network diagram looks bad on the screen. Since no one (except the random number generator, which is not willing to testify) understands the current structure of the network, a radical decision was made: remove $k$ of the skills (along with all their dependencies) so that the complexity degree of the remaining network decreases to the lowest possible value.

Input

The first line of input contains three integers $n, m$, and $k$ ($1 \le n \le 300, 0 \le m \le 400, 0 \le k \le \min(n, 4)$), representing the current number of skills, the number of dependencies, and the number of skills to remove, respectively. The skills are numbered from $1$ to $n$.

The next $m$ lines each contain two numbers $x$ and $y$ ($1 \le x < y \le n$), meaning that before learning skill $y$, one must know $x$. You may assume that the dependencies were generated randomly, using the method described in the problem statement.

Output

Output a single number – the minimum possible complexity degree of the skill network after removing at most $k$ of them.

Examples

Input 1

6 5 1
1 3
2 3
3 4
4 5
4 6

Output 1

2

Note 1

If you remove skill number 4, the longest chain will have a length of 2 (for example $1 \to 3$ or $2 \to 3$). Thus, the minimum possible complexity degree is 2 – you are not able to remove one skill to obtain a degree of 1.

Input 2

3 3 3
1 2
1 3
2 3

Output 2

0