Description

小A在游戏中扮演了一个高效的指挥官，他遇到了这个问题：

A国爆发了战争，伟大的人民起义军需要夺回城市的控制权。

已知A国有 座城市，其中有 条道路连接着它们。起义军的载具只能在互相联通的城市中使用，若两座城市不直接或者间接联通则需要修筑道路。

起义军共有 单位的时间，在单位时间内他们可以执行以下操作之一：

• 占领任何一座未被占领的城市（不考虑此时起义军的位置）。
• 在任意两座城市间修建一条道路。
• 指挥所有被占领城市生产分别一个单位的资源。

起义军初始位置永远为编号为 的城市（所以这个城市不需要时间占领）。

Input Format

在第一行有三个整数 $t, n, m(0 \le t, n \le 10^6, 0 \le m\le 10^3)$ ，分别代表总行动时间，城市数量与道路数量。

在接下来的 $m$ 行，每行有两个整数 $u, v$ 代表编号为 $u, v$ 的城市之间有道路连接。

Output Format

输出共一行，为最大生产总量。

3 2 1
1 2​

4