3에 깃든 힘

면접 대비

시간 제한2초메모리 제한1024 MB

요약

N개 역으로 이루어진 트리를 연결된 3개 역씩 묶은 N/3개의 그룹으로 나눌 수 있는지 판별합니다. 가능하면 그룹을 출력합니다.

난이도: 보통10점 중 5점
유형: 트리, DFS, 그리디
정답자: 아직 제출이 없습니다

문제

서기 3333년, 서울대학교는 명맥을 이어 가며 '한국인학부'를 새로 개설한다. 이 학부에서는 한국인이 오래전부터 좋아해 온 숫자 3을 연구하며, 특히 세상의 모든 것을 3개 단위로 쪼개는 일에 몰두하고 있다. 한국인은 예로부터 3개씩 모인 것에 특수한 힘이 깃든다고 여겨 왔기 때문이다.

물리천문학부 출신으로 컴퓨터공학과 한국인학을 복수전공하는 스누피도 이 흐름에 맞춰 졸업논문을 쓰려고 한다. 깊이 고민한 끝에 스누피는 트리 형태의 지하철 노선을 연결된 역 3개 단위로 묶을 수 있는지 알아보는 연구를 계획한다. 그러나 중급물리실험을 재수강하느라 잘 시간도 부족해서, 스누피에게는 이 문제를 고민할 시간이 없다.

당신이 스누피를 도와 트리 형태의 지하철 노선을 연결된 3개의 지하철 역 단위로 쪼갤 수 있는지 판별하고, 가능하다면 그 방법을 알아내자.

입력

첫째 줄에 지하철 역 개수인 정수 $N$ 이 주어진다. ( $3 \le N \le 333333$ , $N$ 은 3의 배수이다.)

둘째 줄부터 $N-1$ 개의 줄에 걸쳐 지하철 역 번호를 나타내는 두 정수 $u_i$ , $v_i$ 가 공백을 사이에 두고 주어진다. ( $1 \le u_i, v_i \le N$ ) 이는 지하철 노선에서 $u_i$ 번 역과 $v_i$ 번 역이 직접 연결되어 있다는 뜻이다.

출력

첫째 줄에 지하철 노선을 문제의 조건대로 묶을 수 있으면 S를, 그럴 수 없으면 U를 출력한다.

S를 출력했다면 둘째 줄부터 $\frac{N}{3}$ 개의 줄에 걸쳐 각 줄마다 정수 3개를 공백을 사이에 두고 출력한다. 출력하는 모든 정수는 1에서 $N$ 사이의 서로 다른 정수여야 하며, 각 줄의 세 정수는 한 묶음에 속한 세 역의 번호여야 한다. 묶음의 순서와 묶음 안 역 번호의 순서는 자유롭게 출력해도 된다.

예제4

예제 1
입력
```
6
1 2
2 3
3 4
4 5
4 6
```
예상 출력
```
S
1 2 3
4 5 6
```
예제 2
입력
```
3
1 2
2 3
```
예상 출력
```
S
1 2 3
```
예제 3
입력
```
6
1 2
2 3
2 4
4 5
2 6
```
예상 출력
```
U
```

예제 4

입력

예상 출력