Binary Search Tree

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

Someone in a Telegram chat

A binary search tree is a rooted tree in which:

• each vertex has 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 be a binary search tree when rooted at some vertex? If so, which vertices can be the 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$), an edge of the tree.

If the tree cannot be a binary search tree, print -1.

Otherwise, print all vertices that can be the root, in increasing order.