21566번 - 트리 정리하기 서브태스크스페셜 저지

제2회 PMCC의 성공적인 개최를 기원하기 위해, 작년 크리스마스에 대회 운영진들은 크리스마스 트리를 꾸몄습니다. 물론 모두가 한 곳에 모여서 꾸미면 5인 이상 집합 금지 규정을 위반하는 것이기 때문에, 한 번에 네 명을 넘는 인원이 크리스마스 트리를 꾸밀 수 없었습니다.

크리스마스 트리는 $N$개의 정점을 $N-1$개의 간선이 연결하는 연결 그래프, 즉 트리(tree)의 형태를 하고 있었습니다. 그런데 트리의 구조가 너무 복잡했기 때문에, 운영진은 트리를 꾸미기 전에 먼저 트리를 정리하기로 했습니다.

한 번에 네 명 이상이 모일 수 없었기 때문에, 운영진은 아래와 같은 ‘작업’을 반복해서 트리를 정리하기로 했습니다.

• 운영진 네 명은 각각 네 개의 정점 $A$, $B$, $C$, $D$를 한 명당 하나씩 잡습니다. 이때 운영진들이 코로나 시국에서 외로움을 느끼지 않게 하기 위해서, $A$와 $B$, $B$와 $C$, $C$와 $D$는 각각 간선으로 이어져 있어야 합니다.
• $A$, $B$, $C$, $D$ 사이의 모든 간선을 제거합니다.
• $A$와 $C$, $A$와 $D$, $B$와 $D$ 사이에 간선을 추가합니다.

이를 그림으로 나타내면 다음과 같습니다.

초기 상태	작업 뒤의 상태

운영진의 목표는 트리에 몇 번의 작업을 거쳐, 트리의 ‘지름’을 4 이하로 만드는 것입니다. 트리의 지름은 가장 먼 두 정점 사이의 거리를 말합니다. 운영진이 트리를 정리할 수 있는지 판별하고, 정리할 수 있으면 방법을 아무거나 하나 찾는 프로그램을 만들어 봅시다.

첫 줄에는 트리의 정점의 수 $N$이 주어집니다. 다음 줄부터 개의 줄에는 트리의 각 간선으로 연결된 정점의 번호 $u_i$, $v_i$가 주어집니다.

만약 유한 번의 작업으로 트리를 정리하는 것이 불가능하다면, $-1$을 출력하고 프로그램을 종료합니다.

만약 트리를 정리하는 것이 가능하다면, 첫 줄에는 작업의 횟수 $Q$를 출력합니다.

다음 줄부터 개의 줄에는 네 정수 $A$, $B$, $C$, $D$를 출력합니다. 각 정수는 위에서 언급된 ‘작업’의 규칙에 해당하는 네 정점의 번호여야 합니다.

• $4 \le N \le 10^3$
• 입력에서 주어진 그래프는 올바른 트리를 형성함이 보장됩니다.
• $0 \le Q \le 10^3$
• $1 \le A, B, C, D \le N$
• $A$, $B$, $C$, $D$는 모두 서로 다릅니다.
• 각 작업 전에 정점 $A$와 정점 $B$, 정점 $B$와 정점 $C$, 정점 $C$와 정점 $D$는 모두 서로 연결되어 있어야 합니다.
• 유한 번 내의 작업으로 트리를 정리할 수 있다면, 위 제한을 만족하는 트리 정리 방법 역시 존재함이 보장됩니다.