# [Gold II] 구름다리 [문제 링크](https://www.acmicpc.net/problem/22967) ## 문제 설명 <p>선린인터넷고등학교에는 여러 건물과 그 건물들을 연결하는 구름다리가 있다.</p> <p>구체적으로, $1$번부터 $N$번까지의 번호가 붙은 건물 $N$개와, 서로 다른 두 건물을 잇는 구름다리 $N-1$개가 있다.</p> <p>모든 건물들은 구름다리들을 통해 직, 간접적으로 연결되어 있다.</p> <p> </p> <p>2019년도 천하제일 토목건축대회 우승자인 정휘는 구름다리가 너무 적어서 건물 사이를 이동하기 힘들다고 느꼈다.</p> <p>그래서 정휘는 2018년도 준우승자인 노현이를 고용해 구름다리를 추가로 건설하기로 했다.</p> <p>노현이는 최대 $N-1$개의 구름다리를 추가로 건설해서, 선린인터넷고등학교의 지름을 최대한 작게 만들어야 한다.</p> <p>학교의 지름이란, 학교의 <strong>두 건물 사이를 구름다리로만 이동할 때 거쳐야 하는 구름다리 개수의 최댓값</strong>을 뜻한다.</p> <p>지름을 최대한 작게 하려면, 구름다리를 어떻게 건설해야 할까?</p> ## 입력 <p>첫째 줄에 건물의 개수 $N$이 주어진다.</p> <p>둘째 줄부터 $N-1$개의 줄에 걸쳐, 이미 존재하는 구름다리들이 연결하고 있는 서로 다른 두 건물의 번호가 한 줄에 하나씩 주어진다.</p> ## 출력 <p>첫째 줄에는 학교의 지름을 최대한 작게 만들기 위해 노현이가 추가로 건설해야 하는 구름다리의 개수 $K$를 출력한다. ($0 le K le N-1$)</p> <p>둘째 줄에는 노현이가 아래에 출력할 방법으로 $K$개의 구름다리를 추가로 건설한 뒤 학교의 지름 $R$을 출력한다.</p> <p>셋째 줄부터 $K$개의 줄에 걸쳐, 건설할 구름다리들이 연결할 서로 다른 두 건물의 번호를 한 줄에 하나씩 출력한다.</p> <p>출력하는 구름다리들은 모두 서로 달라야 하며, 이미 존재하는 구름다리를 다시 건설할 수는 없다.</p> <p>출력한 방법대로 구름다리를 건설했을 때 학교의 지름이 $R$이 되고, 이 값 $R$이 $N-1$개 이하의 구름다리를 건설해서 만들 수 있는 지름의 최솟값과 같다면, 출력은 정답으로 채점된다.</p> ## 풀이 #### n이 4 이하일 때는 모든 정점을 연결하여 지름이 1일 수 있습니다. n이 5 이상일 때는 모든 정점을 한 정점에 연결해 지름을 2로 만들 수 있습니다. ``` c++ #include<bits/stdc++.h> using namespace std; bool canMove[300][300]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i=0;i<n-1;i++) { int a, b; cin >> a >> b; canMove[a-1][b-1]=canMove[b-1][a-1]=true; } vector<pair<int, int>> res; if(n<=4) { for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { if(!canMove[i][j]) res.push_back({i+1, j+1}); } } cout << res.size() << "\n1\n"; } else { for(int i=1;i<n;i++) { if(!canMove[0][i]) res.push_back({1, i+1}); } cout << res.size() << "\n2\n"; } for(auto e:res) cout << e.first << ' ' << e.second << '\n'; } ```