주군 또한 이 모든 일에서 자신의 충실한 봉신에게 같은 의무를 다해야 한다.
- 샤르트르의 풀베르, 아키텐 공작 기욤에게 보낸 편지(1020년)
당신은 왕국의 도로를 담당하는 관리인데, 최근 들어 들끓기 시작한 노상강도로 인해 골머리를 앓고 있다. 이 상황을 해결하기 위해 국왕은 휘하의 영주들에게 기사를 내어 경비대를 꾸리고 도로의 치안과 안전을 지키도록 명하고자 한다. 그러나 영주마다 내어 줄 수 있는 기사의 수가 달라 모든 도로에 기사를 배정할 수 있는 것은 아니다.
왕국에는 국왕을 포함하여 번부터 번까지 번호가 붙은 명의 영주가 있다. 번 영주는 국왕이다. 국왕을 제외한 각 영주는 한 명의 주군을 섬기며 그 주군의 봉신이다. 어느 영주에서든 주군을 거슬러 올라가면 국왕에 이른다.
각 영주는 영지라고 부르는 자신의 땅을 하나씩 다스린다. 번 영주의 주군은 번 영주이며 국왕을 제외한 각 영주의 영지는 자신의 주군의 영지와 도로 하나로 연결되어 있다.
왕국에는 주군과 봉신 관계가 아닌 영주들의 영지를 연결하는 도로도 있을 수 있다. 그러나 국왕은 주군과 봉신 사이의 왕래를 우선 보호하려 한다. 따라서 경비대를 배정할 대상은 각 영주의 영지와 자신의 주군의 영지를 연결하는 도로로 한정한다. 그 밖의 도로는 이 문제에서 고려하지 않는다.
각 도로에 배정할 경비대는 그 도로 양쪽의 영주가 기사 한 명씩을 내어 꾸린다. 번 영주는 치안 유지에 참여할 기사 명을 내어 줄 수 있다. 각 기사는 하나의 경비대에만 참여할 수 있으며 한 도로에는 경비대를 하나만 배정할 수 있다. 모든 기사를 배정할 필요는 없다.
경비대가 배정된 도로는 안전한 도로가 된다. 대상 도로 중 안전한 도로의 수가 최대가 되도록 경비대를 배정했을 때 그 수를 구하여라.
첫째 줄에 영주의 수 이 주어진다.
둘째 줄에 이 공백으로 구분되어 주어진다.
안전한 도로의 최대 개수를 출력한다.
첫 번째 예제에서는 번과 번 영지 사이의 도로와 번과 번 영지 사이의 도로와 번과 번 영지 사이의 도로에 경비대를 배정할 수 있다. 대상 도로는 모두 번 또는 번 영지와 연결되어 있으며 두 영주가 내어 줄 수 있는 기사는 총 명이므로 개 이상의 도로에 경비대를 배정할 수는 없다.
셋째 줄에 이 공백으로 구분되어 주어진다.
두 번째 예제에서는 대상 도로가 모두 국왕의 영지와 연결되어 있다. 국왕이 내어 줄 수 있는 기사가 없으므로 경비대를 배정할 수 없다.
