Nate wants to have more people join his contest. However, he doesn't have much time. He can only directly send invitations to $k$ people. Thankfully, if he invites someone, that person can tell all of his friends about the contest, and those friends can tell all of their friends, and so on.
Suppose that there are $n$ people and $m$ pairs of them are friends. What is the maximum number of people he can invite?
The first line of input contains three space-separated integers $n$, $m$, and $k$, respectively. The first integer, $n$, is the number of people. The second integer, $m$, is the number of pairs of friends. The third integer, $k$, is the number of invitations Nate can directly send.
The next $m$ lines of input each contain two space-separated strings, the names of a pair of friends. Each name is composed of only lowercase English letters and doesn't exceed 10 letters in length.
*Constraints*
$1 <= n <= 10^5$
$1 <= m <= 10^5$
$1 <= k <= min (n, 100)$
Output a single integer, the maximum number of people Nate can invite.
In the first test case, Nate can invite Anne, who invites both her friends Billy and Charles.
In the second test case, Nate can invite Dave, who invites Earl, who invites Fontana. There is no way to invite all six people, as none of Dave, Earl, and Fontana are friends with Gillian, Heather, or Ian.
In the third test case, Nate can invite Joshua, Lily, and Ned, who then invite Karla, Mark, and Oliver respectively.
## Input
The first line of input contains three space-separated integers $n$, $m$, and $k$, respectively. The first integer, $n$, is the number of people. The second integer, $m$, is the number of pairs of friends. The third integer, $k$, is the number of invitations Nate can directly send.The next $m$ lines of input each contain two space-separated strings, the names of a pair of friends. Each name is composed of only lowercase English letters and doesn't exceed 10 letters in length.*Constraints*$1 <= n <= 10^5$ $1 <= m <= 10^5$ $1 <= k <= min (n, 100)$
## Output
Output a single integer, the maximum number of people Nate can invite.
[samples]
## Note
In the first test case, Nate can invite Anne, who invites both her friends Billy and Charles.In the second test case, Nate can invite Dave, who invites Earl, who invites Fontana. There is no way to invite all six people, as none of Dave, Earl, and Fontana are friends with Gillian, Heather, or Ian.In the third test case, Nate can invite Joshua, Lily, and Ned, who then invite Karla, Mark, and Oliver respectively.
**Definitions**
Let $ s = (|\mu(1)|, |\mu(2)|, |\mu(3)|, \dots, |\mu(10^9)|) $ be an infinite sequence where $ \mu(n) $ is the Möbius function:
$$
\mu(n) =
\begin{cases}
0 & \text{if } n \text{ has a squared prime factor}, \\
(-1)^k & \text{if } n \text{ is the product of } k \text{ distinct primes}, \\
1 & \text{if } n = 1.
\end{cases}
$$
Let $ t \in \{0,1\}^{200} $ be the given binary string formed by concatenating 10 lines of 20 characters each.
**Constraints**
- $ t $ is a binary string of length 200.
- $ s $ is defined for all $ x \in \{1, 2, \dots, 10^9\} $.
- We seek the minimal $ p \in \mathbb{Z}^+ $ such that $ |\mu(p+i)| = t_{i+1} $ for all $ i \in \{0, 1, \dots, 199\} $.
**Objective**
Find the smallest positive integer $ p $ such that
$$
\forall i \in \{0, 1, \dots, 199\}, \quad |\mu(p + i)| = t[i]
$$
If no such $ p \leq 10^9 - 199 $ exists, output $ -1 $.