P16237 [Lanqiao Cup 2026 NOI Qualifier B] Emergency Wiring.

In a laboratory, Xiaolan is responsible for maintaining a local area network consisting of $N$ computers. These computers were originally connected by high-speed network cables, but as the equipment has aged, only $M$ cables are still working. Because of this, the once unified network has split into several mutually disconnected communication regions. To restore communication, Xiaolan plans to install a special kind of “emergency patch cable” to reconnect these regions. In terms of connectivity, as long as any two computers can establish a direct or indirect path using the remaining working cables or the newly installed emergency patch cables, they are considered connected again. Xiaolan’s task is to choose an optimal wiring plan so that all $N$ computers in the laboratory become fully connected again. Because the ports for emergency patch cables consume valuable hardware resources on the computers, Xiaolan sets two priority levels when making the plan. First, the total number of emergency patch cables used must be minimized in theory. Second, to reduce the load on any single computer, he wants these patch cables to be shared as evenly as possible. Specifically, he needs to find a plan such that, among all computers, the one with the most emergency patch cables connected to it has that number as small as possible. Now, based on the current remaining cable connections, compute the minimum number of emergency patch cables needed to achieve full connectivity, and under this optimal premise, the minimum possible value of the maximum number of emergency patch cables connected to any single computer.

The first line contains two integers $N$ and $M$, representing the total number of computers and the number of currently working network cables. The next $M$ lines each contain two integers $a$ and $b$, indicating that there is currently a working cable between computer $a$ and computer $b$.

Output one line containing two integers separated by a single space. The first integer is the minimum number of emergency patch cables that must be added. The second integer is, under the premise that the total number of patch cables is minimal, the minimum possible value of the maximum number of emergency patch cables connected to any single computer.

### Sample Explanation. :::align{center}  ::: By connecting $1-4$, $4-5$, $5-6$, $6-7$ (a total of 4 patch cables), nodes $4,5,6$ each take on two patch cables, while the other nodes take on only one or none, so the maximum value is minimized to $2$. ### Constraints and Notes. For $30\%$ of the testdata, $1 \le N \le 100$, $0 \le M \le 100$. For all testdata, $1 \le N \le 10^5$, $0 \le M \le 10^5$, $1 \le a,b \le N$, $a \ne b$. It is guaranteed that the input connections contain no multiple edges. Translated by ChatGPT 5