우리는 진실을 잊고 살잖아

시간 제한1초메모리 제한1024 MB

요약

정점 n개와 간선 m개가 주어진 그래프에서 무작위로 공개되는 간선 여부 쌍을 보다가 그래프가 연결인지 판단할 때까지 필요한 최소와 최대 쿼리 수를 구합니다.

난이도: 어려움10점 중 8점
유형: 그래프, 조합론, 그리디, 완전 탐색
정답자: 아직 제출이 없습니다

문제

우리는 무방향 단순 그래프 $G$ 를 WE11 no. N이라는 프로그램에 넣어 놓았다. $G$ 의 각 정점에는 $1, 2, \ldots, N$ 의 번호가 붙어 있다. 이 프로그램은 각 정점 쌍마다 간선의 존재 여부를 알려준다. 구체적으로,

$1 \le a < b \le N$ 인 모든 자연수쌍 $(a, b)$ 의 목록을 무작위로 섞는다.
목록 순서대로, 각 $(a, b)$ 마다 $a$ 와 $b$ 를 연결하는 간선이 있는지 일정 시간 간격으로 알려준다. 사용자가 원하는 때에 프로그램을 종료할 수 있다.

안타깝게도, 우리는 진실을 잊고 살기 때문에 더 이상 $G$ 가 어떻게 생겼는지 전혀 모른다. 그 상태에서 WE11 no. N을 실행해서 $G$ 가 연결 그래프인지, 즉 어떤 두 정점을 잡더라도 두 정점 사이의 경로가 존재하는지 여부를 알아내려고 한다. 우리는 이 프로그램으로 모은 정보만으로 $G$ 가 연결 그래프인지 여부를 알 수 있게 되는 순간 프로그램을 종료할 것이다.

프로그램을 종료했을 때까지 모으게 되는 정보는 최소 몇 개, 최대 몇 개일까? 불쌍한 김우리를 도와주자.

입력

첫 줄에 $G$ 의 정점의 개수 $N$ 과 간선의 개수 $M$ 이 주어진다. ( $2 \le N \le 500$ , $0 \le M \le N(N-1)/2$ ) 다음 $M$ 줄에는 한 줄에 하나씩 한 간선이 연결하는 두 정점의 번호가 주어진다.

출력

첫 번째 줄에 최소 몇 개의 정보를 모으게 될지 출력한다. 두 번째 줄에 최댓값을 출력한다.

예제2

예제 1
입력
```
3 3
1 2
2 3
3 1
```
예상 출력
```
2
2
```
예제 2
입력
```
3 1
1 2
```
예상 출력
```
2
3
```