이진 탐색 트리

트리가 이진 탐색 트리인지 어떻게 확인할까?

텔레그램 채팅방의 한 사람

이진 탐색 트리는 뿌리가 있는 트리이며 다음 조건을 만족한다.

• 각 정점은 왼쪽 자식을 최대 하나, 오른쪽 자식을 최대 하나 가진다.
• 리프가 아닌 각 정점 $x$에 대해, 왼쪽 부분 트리의 모든 정점은 $x$보다 작고, 오른쪽 부분 트리의 모든 정점은 $x$보다 크다.

정점이 $n$개인 트리가 주어진다. 이 트리를 어떤 정점을 뿌리로 하여 이진 탐색 트리로 만들 수 있는지 확인하라. 만들 수 있다면 뿌리가 될 수 있는 정점을 모두 구하라.

첫째 줄에 트리의 정점 개수 $n$ ($1 \le n \le 500000$)이 주어진다.

이어지는 $n - 1$개의 줄에는 트리의 간선을 나타내는 정수 두 개 $u_i$, $v_i$ ($1 \le u_i, v_i \le n$)가 한 줄에 하나씩 주어진다.

트리를 이진 탐색 트리로 만들 수 없으면 -1을 출력한다.

그렇지 않으면 뿌리가 될 수 있는 정점을 모두 오름차순으로 출력한다.