컴퓨터 네트워크
시간 제한2초메모리 제한512 MB
방향 그래프에서 모든 컴퓨터에 도달할 수 있는 최소 시작 컴퓨터 수와, 어느 컴퓨터에서든 모든 컴퓨터에 도달하도록 만들기 위해 추가해야 하는 최소 연결 수를 구한다.
문제
컴퓨터 네트워크는 0번부터 N-1번까지 번호가 붙은 N대의 컴퓨터로 이루어진다. 컴퓨터는 메시지를 받으면 그 메시지를 다른 여러 컴퓨터로 전달한다. 컴퓨터 X에서 보낸 메시지가 컴퓨터 Y에 도달하더라도, Y에서 보낸 메시지가 X에 도달한다는 보장은 없다. 관리자는 네트워크의 모든 컴퓨터에 메시지를 전달하기 위해 메시지를 보낼 컴퓨터를 최소 몇 대 골라야 하는지 알고 싶어 한다.
메시지를 더 잘 전달하기 위해 관리자는 네트워크를 확장하여 여러 컴퓨터 사이에 새 연결을 추가하기로 했다. 그러면 어느 컴퓨터에서 메시지를 보내든 다른 모든 컴퓨터로 퍼진다. 이를 위해 모든 컴퓨터를 메시지 배포의 시작점으로 쓸 수 있도록 추가해야 하는 새 연결의 최소 개수를 구해야 한다.
프로그램 cnet을 작성하여, 네트워크의 모든 컴퓨터에 메시지를 전달하기 위해 메시지를 보내야 하는 컴퓨터의 최소 대수와, 어느 컴퓨터에서 보낸 메시지든 다른 모든 컴퓨터에 도달하도록 하기 위해 추가해야 하는 새 연결의 최소 개수를 구하시오.
입력
표준 입력의 첫째 줄에 정수 N과 M이 주어진다. 각각 컴퓨터의 수와 컴퓨터 사이의 연결의 수이다. 다음 M개 줄에 연결이 하나씩 주어진다. 첫 번째 수는 메시지를 보내는 컴퓨터의 번호이고, 두 번째 수는 메시지를 받는 컴퓨터의 번호이다.
출력
표준 출력의 한 줄에 정수 두 개를 출력한다. 네트워크 전체에 메시지를 배포하기 위한 시작점으로 쓰이는 컴퓨터의 최소 대수와, 임의로 고른 컴퓨터에서 보낸 메시지가 다른 모든 컴퓨터에 도달하도록 네트워크를 확장하는 데 필요한 추가 연결의 최소 개수이다.
제한
- 1 < N ≤ 1 600
- 0 ≤ M ≤ 120 000