25622번 - 3에 깃든 힘 스페셜 저지

때는 서기 3333년, 서울대학교는 그 명맥을 유지하며 ‘한국인학부’라는 새로운 학부가 개설되기에 이른다. 해당 학부에서는 한국인이 오래 전부터 좋아하는 숫자인 3에 관한 연구가 활발히 이루어지고 있었는데, 특히 세상의 모든 것들을 3개 단위로 쪼개는 일에 몰두하고 있었다. 한국인들은 예로부터 3개씩 모인 것들에 어떤 특수한 힘이 깃든다고 생각했기 때문이다.

물리천문학부 출신이며 컴퓨터공학과 한국인학을 복수전공하고 있는 스누피 또한 이런 흐름에 편승하여 졸업논문을 작성하려고 한다. 깊은 고뇌 끝에 스누피는 트리 형태의 지하철 노선을 연결된 역 3개 단위로 묶을 수 있는지 알아보려는 연구를 계획하기에 이른다. 하지만 중급물리실험 재수강으로 인해 잘 시간도 부족한 스누피는 이 문제를 고민할 시간이 없다.

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

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

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

첫째 줄에 지하철 노선을 문제에서 요구하는 대로 묶을 수 있다면 S를, 그럴 수 없다면 U를 출력한다.

만약 첫째 줄에 S를 출력했다면 둘째 줄부터 N3줄에 걸쳐 각 줄에 3개의 정수를 공백을 사이에 두고 출력한다.

둘째 줄부터 출력하는 모든 정수는 서로 다른 1에서 N 사이의 정수여야 하며, 각 줄의 세 정수는 문제에서 요구하는 대로 묶었을 때 묶은 단위의 세 역의 번호여야 한다. 묶은 단위의 순서나 묶은 단위 내의 역 번호의 순서는 마음대로 하여 출력해도 좋다.