Description

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.

Input Format

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.

Output Format

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.

2
8 4
4 4

7 4
2 2

Hint

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.

For all data, $1\le T\le 10^5$, $1\le n\le 10^9$, $0\le m\le \dfrac{n(n-1)}{2}$.