트리를 나타내는 간선들의 정보가 주어질 때, 간선 2개를 제거하여 부분 트리 세 개로 만들려고 한다.

이 때, 각 부분트리의 노드 개수가 모두 같아야 한다. 다음은 노드가 9개인 트리의 예시이다.

위 그림에서 동그라미 안에 적힌 숫자는 노드번호, 간선에 적힌 숫자는 간선 번호를 나타낸다.

위 예시와 같이 붉은색 간선(2번, 5번)을 제거하면 세 부분 트리로 나뉘며,

각 부분 트리에 속한 노드 개수는 3개로 모두 같다.

이때, 세 부분으로 분리된 부분 트리는 노드 수만 같으면 되며,

트리의 모양까지 같을 필요는 없다.

트리의 노드 개수와, 트리의 간선 정보가 주어질 때,

노드 수가 같은 부분 트리 세 개로 분리하기 위해 제거해야 하는 두 간선의 번호를

오름차순으로 출력하는 프로그램을 작성하시오.

트리 나누기 timer 1s memory 256MB

트리 나누기 1s 256MB