시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (언어별 추가 시간 없음) 1024 MB 26 11 9 42.857%

문제

우리는 무방향 단순 그래프 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줄에는 한 줄에 하나씩 한 간선이 연결하는 두 정점의 번호가 주어진다.

출력

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

예제 입력 1

3 3
1 2
2 3
3 1

예제 출력 1

2
2

간선이 어떤 순서로 출력되더라도 정확히 두 번만에 G가 연결그래프임을 알 수 있다.

예제 입력 2

3 1
1 2

예제 출력 2

2
3

최소의 경우 (1, 3)과 (2, 3)이 나오면 G가 연결그래프가 아님을 알 수 있다. 최대의 경우 (1, 2), (1, 3), (2, 3)이 나오면 G가 연결그래프가 아님을 알 수 있다. 물론 최소와 최대의 경우는 주어진 순서 외에도 많이 존재한다.

출처

Contest > 웰노운컵 > 제2회 웰노운컵 Day 2 G번