Дано укоренённое бинарное дерево на N вершинах. Скажем, что вершина v находится на границе дерева, если она подходит под любое из условий:
- v является листом;
- пусть v находится на расстоянии h от корня. Тогда v — самая левая или самая правая вершина среди всех вершин на расстоянии h от корня.
Найдите все вершины, находящиеся на границе дерева.
В первой строке записаны два целых числа: количество вершин в дереве n (1 ≤ n ≤ 2⋅105) и rootid (0 ≤ rootid ≤ n−1) — номер вершины-корня.
В следующих n строках описаны вершины. Каждая вершина описывается двумя числами, записанными через пробел: id левого потомка и id правого потомка. Все id находятся в диапазоне [0;n−1]. Если у вершины нет какого-то потомка, то вместо его id будет − 1.
Гарантируется, что входные данные корректны.
В единственной строке через пробел выведите в любом порядке все id вершин, которые находятся на границе дерева. Каждая вершина должна быть выведена не более одного раза.
|
10 0 1 2 3 4 5 6 7 -1 8 -1 -1 -1 9 -1 -1 -1 -1 -1 -1 -1 |
5 8 9 1 0 7 3 2 6 |