케이블 보호

ICPC(International Cable Protection Company)는 네트워크 스위치에 설치해 그 스위치에 연결된 모든 케이블 링크가 제대로 동작하는지 감시하는 케이블 보호 도구를 만든다. 이 보호 도구는 전송 지연을 일으키므로 모든 스위치에 설치하기에는 적합하지 않다.

보통 네트워크 토폴로지는 백본과 여러 서브넷의 두 부분으로 이루어진다. 백본의 스위치는 링 구조로 연결되고, 각 백본 스위치는 서브넷의 루트가 되며 서브넷의 스위치는 트리 구조로 연결된다. 이런 토폴로지를 단일 사이클 토폴로지라고 한다. 그림 2는 단일 사이클 토폴로지의 예이다.

그림 2: 단일 사이클 토폴로지의 예.

백본 스위치가 n개, 서브넷 스위치가 m개 있다고 하자. 스위치에는 0부터 m + n − 1까지의 정수가 번호로 붙는다. 백본 스위치는 시계 방향 순서로 0부터 n − 1까지 번호가 붙고, 서브넷 스위치는 n부터 n + m − 1까지 번호가 붙는데, 각 서브넷 스위치의 번호는 속한 서브넷의 루트 트리 구조에서 부모의 번호보다 크다. 그림 3은 스위치 번호 부여의 예이다.

그림 3: 스위치 번호 부여의 예.

ICPC를 위해 모든 케이블 링크를 감시할 수 있도록 케이블 보호 도구를 설치할 스위치의 최소 개수를 정하는 프로그램을 작성하라. 그림 4는 주어진 네트워크에 대한 최적해를 보여준다(타원으로 표시).

그림 4: 주어진 네트워크에 대한 최적해.

입력 파일의 첫째 줄에 백본 스위치의 수와 서브넷 스위치의 수를 나타내는 두 정수 n과 m이 공백 하나를 사이에 두고 주어진다. 다음 n+m개 줄은 각각 링크의 양 끝 스위치 번호를 나타내는 두 정수가 공백 하나를 사이에 두고 주어진다.

모든 케이블 링크를 감시할 수 있도록 케이블 보호 도구를 설치할 스위치의 최소 개수를 출력한다.

• 3 ≤ n ≤ 100000
• 1 ≤ m ≤ 100000