16230번 - 우리는 진실을 잊고 살잖아

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

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

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

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

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

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