Binary Search Tree

아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제 설명

예제4

문제

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.