405702: GYM102051 C Nate and Contest Invitation

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 \le n \le 10^5$$$

$$$1 \le m \le 10^5$$$

$$$1 \le k \le \min\left(n, 100\right)$$$

Output a single integer, the maximum number of people Nate can invite.

3 2 1
Anne Billy
Anne Charles

3

6 4 1
Dave Earl
Earl Fontana
Gillian Heather
Heather Ian

3

6 3 3
Joshua Karla
Lily Mark
Ned Oliver

6

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.