Maximizing Landmarks Visited

You are given a bidirectional graph with n cities and m flight routes. Each city has a unique landmark. You start your journey from city 1 and have k days available. Every day, you can choose to either stay in your current city or travel to any adjacent city (i.e. there exists a flight route between the cities).

Whenever you visit a city, its landmark is counted toward your total; however, each landmark is counted only once even if you visit the same city multiple times. Your task is to determine the maximum number of distinct landmarks you can visit in at most k days.

You can think of the set of visited landmarks mathematically as:

$$\text{visited\_count} = \sum_{i=1}^{n} \mathbf{1}_{\{\text{city } i \text{ is visited}\}} $$

Note that the journey starts in city 1 with its landmark already visited.

inputFormat

The first line of input contains three integers (n), (m) and (k) representing the number of cities, the number of bidirectional flight routes, and the number of days available respectively. Each of the following (m) lines contains two integers (u) and (v), indicating a flight route between city (u) and city (v).

outputFormat

Output a single integer which is the maximum number of distinct landmarks that can be visited within (k) days.## sample

4 4 3
1 2
1 3
2 4
3 4

3