Optimal Bakery Placement Problem

You are given N towns numbered from 1 to N and you are to open M bakeries in these towns. There are some bidirectional roads connecting the towns. Your task is to choose M towns to open the bakeries such that the maximum distance any town has from its nearest bakery is minimized.

Formally, if a bakery is opened in town i, then any town j will have a distance d(j, i) (the length of the shortest path in the graph). When bakeries are opened in a set S of towns, the distance of town j to the nearest bakery is min_i∈S d(j, i). Let D be the maximum of these distances over all towns. Your objective is to choose S so that D is minimized.

This can be stated as minimizing:

$$ D = \min_{S \subseteq \{1,2,\dots,N\}, |S|=M} \max_{j=1}^{N} \min_{i \in S} d(j,i) $$

inputFormat

The input is read from stdin and has the following format:

• The first line contains three integers N, M and R, where N is the number of towns, M is the number of bakeries to open, and R is the number of roads.
• The next R lines each contain two integers u and v which indicate that there is a bidirectional road connecting town u and town v.

outputFormat

Output a single integer to stdout, which is the minimum possible maximum distance any town will have from its nearest bakery when the bakeries are placed optimally.

## sample

5 2 4
1 2
1 3
3 4
3 5

1