P10378 [GESP202403 Level 7] Communication Problem

Related multiple-choice and true/false questions: .

$n$ students from two schools $A$ and $B$ gather together to communicate with each other. For convenience, we number these students from $1$ to $n$. They have conducted $m$ communications. In the $i$-th communication, the students numbered $u_i$ and $v_i$ discussed topics they were interested in and became new friends. Since the purpose of this event is to promote friendship between the two schools, only students from different schools communicate with each other. Students from the same school do not communicate with each other. As an advisor of school $A$, you are very interested in the size of school $B$. You want to find the minimum possible number of students in school $B$, and the maximum possible number of students in school $B$.

The first line contains two positive integers, representing the number of students $n$ and the number of communications $m$. The next $m$ lines each contain two integers $u_i, v_i$, representing one communication.

Output one line with two integers separated by a single space, representing the minimum possible number of students in school $B$ and the maximum possible number of students in school $B$.

### Constraints - For $30\%$ of the testdata, $n \leq 17$, $m \leq 50$. - For $60\%$ of the testdata, $n \leq 500$, $m \leq 2000$. - For all testdata, $1 \leq u_i, v_i \leq n \leq 10^5$, $1 \leq m \leq 2\times 10^5$. The input is valid, meaning that every communication is guaranteed to be between students from different schools. Translated by ChatGPT 5