시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 13 9 9 69.231%

문제

제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$는 모두 서로 연결되어 있어야 합니다.
  • 유한 번 내의 작업으로 트리를 정리할 수 있다면, 위 제한을 만족하는 트리 정리 방법 역시 존재함이 보장됩니다.

서브태스크

번호 배점 제한
1 4

$N \le 6$

2 11

$1 \le i < N$인 모든 정수 $i$에 대해, 정점 $i$와 정점 $i+1$을 잇는 간선이 존재합니다.

3 38

$N \le 50$

4 47

추가 제한 조건이 없습니다.

예제 입력 1

5
1 2
2 3
3 4
4 5

예제 출력 1

1
1 2 3 4

위 예제는 트리의 지름이 처음부터 4 이하이기 때문에, 0을 출력해도 됩니다.

채점 및 기타 정보

  • 예제는 채점하지 않는다.