13041번 - Centipede 스페셜 저지다국어

When Phil was a boy he had a centipede. Everybody knows that centipedes have lots of legs, Phil's one had a total of n legs, some of the legs were left, the other ones were right. Each day the centipede used some of its legs, it always used at least one left leg and at least one right leg.

Each day Phil wrote down two integers to his notebook: the number of left legs and the number of right legs used by the centipede that day.

Phil now wants to use his notes to find out how many left legs and how many right legs his centipede had. However, Phil was not perfectly accurate, so he could make mistakes in his notes. Phil says that his note l_i, r_i is correct if the centipede had at least l_i left legs and at least r_i right legs.

Help Phil to find out how many left legs and how many right legs could his centipede have, so that the maximum number of his notes were correct.

Input contains several test cases. The first line of input contains t — the number of test cases (1 ≤ t ≤ 10 000).

Each test case starts with a line that contains an integer n (2 ≤ n ≤ 10⁹) — the total number of centipede legs. The following line contains m (1 ≤ m ≤ 10⁵) — the number of Phil's notes.

The following m lines contain two integers l_i, r_i each (1 ≤ l_i, r_i ≤ n) — the number of left legs and right legs used by the centipede on the i-th day, according to Phil's notes.

The total number of notes in all test cases in one input data doesn't exceed 10⁵.

For each test case print one line with two integers: the number of left legs and the number of right legs the centipede could have so that the maximum number of notes were correct.