시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

How to check if a tree is a binary search tree?

Someone in a Telegram chat

Binary search tree is a rooted tree, in which:

  • each vertex can have at most one left child and at most one right child,
  • for each non-leaf vertex $x$, all vertices in its left subtree are less than $x$. and all vertices in its right subtree are greater than $x$.

You are given a tree with $n$ vertices. Can this tree, being rooted at some vertex, be a binary search tree, and if it can, what vertices can be a root?

입력

The first line contains an integer $n$ ($1 \le n \le 500000$) --- the number of vertices in the tree.

Each of the next $n - 1$ lines contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$) --- the edges of the tree.

출력

If this tree can't be a binary search tree, output "-1".

Otherwise, output all vertices that can be a root, in increasing order.

예제 입력 1

3
1 2
2 3

예제 출력 1

1 2 3

예제 입력 2

3
1 3
3 2

예제 출력 2

1

예제 입력 3

4
1 3
3 2
2 4

예제 출력 3

-1

예제 입력 4

4
1 2
1 3
1 4

예제 출력 4

-1