Statement
점점 빨라져 점점 즐거워져 점점 빨라져 점점 웃는 얼굴이 돼
— 40mP, 「점점 빨라져」
오늘은 좋은 일이 있어서 기분이 좋은 날. 미쿠는 정점이 개인 가중치가 없는 무향 트리 위에서 산책을 하려고 한다. 각 정점에는 이상 이하의 서로 다른 번호가 매겨져 있다. 기분이 좋은 미쿠는 최대한 오래 산책을 하고 싶다.
아래 조건들을 모두 만족하는 길이가 1 이상인 수열 를 산책 경로로 정의하자.
- 미쿠는 걸을수록 탄력이 붙어 점점 빨라진다. 따라서, 번 정점과 번 정점 사이의 거리는 여야 한다.
- 미쿠는 같은 정점을 두 번 이상 방문하고 싶지 않다. 따라서, 수열 의 모든 원소는 서로 달라야 한다.
미쿠에게 가능한 최대 길이의 산책 경로를 찾아 전해 주자!
트리에서 두 정점 간 거리의 정의
두 정점 사이의 거리란 두 정점을 잇는 유일한 단순 경로에 포함된 간선의 개수다.
Input
첫 번째 줄에 트리의 정점의 수 이 주어진다.
두 번째 줄부터 다음 개의 줄에 트리의 각 간선이 연결하는 두 정점 번호 가 공백으로 구분되어 주어진다. (; )
항상 산책 경로가 하나 이상 존재하는 입력만 주어진다.
Output
첫 번째 줄에 가능한 산책 경로의 최대 길이를 나타내는 정수 를 출력한다.
두 번째 줄에 길이가 인 산책 경로를 나타내는 개의 정수 를 공백을 사이에 두고 출력한다.
가능한 정답이 여러 가지라면 그 중 아무거나 하나 출력한다.
Samples
예제 1
입력
2
1 2
출력
2
1 2
예제 2
입력
8
1 2
3 1
7 3
6 3
4 1
5 1
8 3
출력
4
3 7 8 2
수열 는 산책 경로의 조건을 만족한다. 또한 이보다 길이가 긴 산책 경로가 존재하지 않음을 증명할 수 있다.
는 또 다른 산책 경로의 예이다.