이진 트리 순회

첫 줄에 노드의 개수 n (1 이상 5000 이하) 이 주어집니다. 이어서 n개의 줄에 i번째 줄에 노드 i 의 왼쪽 자식과 오른쪽 자식 번호가 주어집니다. 자식이 없으면 0 입니다. 루트는 1번 노드입니다.

이 트리의 전위 순회, 중위 순회, 후위 순회 결과를 각각 한 줄에 공백으로 구분해 출력하세요. (세 줄)

예시

입력

5
2 3
4 5
0 0
0 0
0 0

출력

1 2 4 5 3
4 2 5 1 3
4 5 2 3 1