시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB0000.000%

## 문제

Every day just after school n children rush out of their classrooms onto the field to play football. They choose two captains among themselves who then divide the remaining children into two teams. The teams do not need to be of the same size – in the extreme case, an overconfident captain may challenge all the other children to join their forces against him! Adam and Betka are the captains for today’s game.

There are m pairs of children who are friends. Two friends playing for the same team are more likely to pass the ball to each other than two non-friends, so they increase the strength of their team. The total strength of a team can therefore be defined as the number of pairs of friends within that team.

Adam thinks a football match is fun when the players score many goals. He would like to maximize the sum of the two teams’ strengths. On the other hand, Betka believes the most enjoyable matches are balanced ones, so she wants to minimize the difference between the teams’ strengths.

Find the largest possible sum of teams’ strengths and the smallest possible absolute difference between teams’ strengths. (These are two independent problems – there may not necessarily be a team division that satisfies both criteria.)

## 입력

The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.

The first line of each test case consists of integers n (n ≥ 2) and m (0 ≤ m ≤ n ⋅ (n − 1)/2). Children are labelled 1, …, n. Adam has number 1 and Betka number 2. Each of the following m lines contains two integers ui, vi (1 ≤ ui < vi ≤ n) meaning that ui and vi are friends. Each pair of friends is only listed once.

## 출력

For each test case, output a single line with two integers: the largest possible sum of teams’ strengths, and the smallest possible difference between the teams’ strengths.

번호배점제한
Easy1

n ≤ 24

Hard2

n ≤ 200

## 예제 입력 1

2

3 3
1 2
2 3
1 3

3 1
1 3


## 예제 출력 1

1 1
1 0


## 힌트

In the first example, it does not matter whether Cyril (child 3) will play with Adam or with Betka. Either way, one of the teams will have strength 1 and the other 0, so the sum of strengths is 1 and their difference is 1. In the second example, letting Cyril play with Adam increases the sum of strengths, but letting him play with Betka keeps the teams more balanced.

## 채점 및 기타 정보

• 예제는 채점하지 않는다.