구름다리

• 우선, n-1개의 에지를 가지고 있는 성게그래프의 지름은 2라는 것을 생각하자.
• 최대 n-1개의 에지를 추가한다면, 성게그래프를 포함하는 그래프로 변환하는 것이 가능하므로, 항상 최대 지름을 2 이하로 만드는 것이 가능하다.
• 그러면 그것보다 지름을 더 줄일수 있는 경우는? 지름이 1이 되려면 완전그래프가 되어야 한다. 완전그래프가 되려면 에지가 C(n,2)개가 필요한데, 우리가 만드는 그래프에서는 원래 있던 에지 n-1개와 새로 추가하는 에지 n-1개를 합쳐 최대 2n-2개의 에지를 가질수 있다. 그러므로 n이 3이나 4일때는 완전 그래프를 만들어서 지름을 1로 만드는 것이 가능하고, n이 5이상일 때에는 완전그래프를 만들수 없으므로, 성게를 만들어서 지름을 2로 만드는것이 최적이다.
• 이제 이대로 구현해주기만 하면 된다. 시간복잡도는 O(n).

"""Solution code for "BOJ 22967. 구름다리".

- Problem link: https://www.acmicpc.net/problem/22967
- Solution link: http://www.teferi.net/ps/problems/boj/22967

Tags: [ad hoc]
"""

import itertools
import sys
from teflib import tree as ttree


def main():
    N = int(sys.stdin.readline())  # pylint: disable=unused-variable
    tree = ttree.create_tree_from_input(N)

    if N == 2:
        print('0')
        print('1')
    elif N <= 4:
        answers = [
            (u, v)
            for u, v in itertools.combinations(range(N), 2)
            if v not in tree[u]
        ]
        print(len(answers))
        print('1')
        for u, v in answers:
            print(u + 1, v + 1)
    else:
        adjs = set(range(1, N)) - set(tree[0])
        print(len(adjs))
        print('2')
        for v in adjs:
            print(1, v + 1)


if __name__ == '__main__':
    main()

• Dependency: teflib.tree.create_tree_from_input