P14478 TeNoHiRa

[テノヒラ](https://music.163.com/song?id=22699102&uct2=U2FsdGVkX1/rYLicBWfNbIcJGy0ZFuK5krT7farcc5M=). > 恋をして。 > > それは泡の様に > > 私の心から消え去っていきました。

Little E has $n$ AIs. They no longer want to solve the maximum independent set problem, so they often gather to play Genshin Impact. Little E noticed that recently fewer AIs are playing Genshin Impact. After investigation, it was found that there are $m$ pairs of AIs in conflict. Specifically, for a conflicting pair $(u,v)$, $u$ and $v$ will **not** play Genshin Impact **simultaneously**. It is guaranteed that no duplicate conflicts are counted, and no AI conflicts with itself. Conflicts are unordered. Little E does not know exactly which AIs are in conflict. But Little E wants to know, in the **best and worst cases**, what is the maximum number of AIs that can play Genshin Impact **simultaneously**. ### Formal Description Find the maximum and minimum possible sizes of the maximum independent set over all undirected simple graphs with $n$ vertices and $m$ edges.

**This problem has multiple test cases.** For each test point, the first line contains a positive integer $T$, indicating the number of test cases. Then, $T$ lines follow, each containing two integers $n, m$ for one test case.

For each test case, output one line. Output two answers separated by a space, indicating the maximum number of AIs playing Genshin Impact simultaneously in the **best and worst cases**.

### Sample Explanation For the first test case: - For the first question, we can construct the graph with edges $(1,2),(1,3),(1,4),(1,5)$. Then AIs $2$ to $8$ can play, so the answer is $7$. - For the second question, we can construct the graph with edges $(1,2),(3,4),(5,6),(7,8)$. Then AIs $1,3,5,7$ can play, so the answer is $4$. For the second test case: - For the first question, we can construct the graph with edges $(1,2),(1,3),(1,4),(2,3)$. Then AIs $3,4$ can play, so the answer is $2$. - The second question has the same construction, so the answer is $2$. ### Data Range There are $5$ test points in this problem, each with equal score. | Data ID | $n\le$ | $T\le$ | Special Constraints | | :-----: | :----: | :----: | :-----------------: | | $1$ | $5$ | $10$ | None | | $2$ | $10^7$ | $10$ | None | | $3$ | $10^9$ | $10^5$ | $m\ge \dfrac{n(n-1)}{2}-3$ | | $4$ | $10^9$ | $10^5$ | $m\le n$ | | $5$ | $10^9$ | $10^5$ | None | For all data, $1\le T\le 10^5$, $1\le n\le 10^9$, $0\le m\le \dfrac{n(n-1)}{2}$.