| Codeforces Round 549 (Div. 2) |
|---|
| Закончено |
Вам дано корневое дерево, вершины которого пронумерованы от $$$1$$$ до $$$n$$$. Дерево — это связный граф без циклов. В корневом дереве есть выделенная вершина, называющаяся корнем.
Предками вершины $$$i$$$ называются все вершины, лежащие на пути от корня до вершины $$$i$$$, кроме самой вершины $$$i$$$. Родителем вершины $$$i$$$ называется ближайший к $$$i$$$ предок $$$i$$$. В данном вам дереве родитель вершины $$$i$$$ имеет номер $$$p_i$$$. Для корня величина $$$p_i$$$ равна $$$-1$$$.
Пример возможного дерева для $$$n=8$$$, корнем является вершина $$$5$$$. Родителем вершины $$$2$$$ является вершина $$$3$$$, а родителем вершины $$$1$$$ является вершина $$$5$$$. Предками вершины $$$6$$$ являются вершины $$$4$$$ и $$$5$$$, а предками вершины $$$7$$$ являются вершины $$$8$$$, $$$3$$$ и $$$5$$$ Вы заметили, что некоторые вершины не уважают других. А именно, если $$$c_i = 1$$$, то вершина $$$i$$$ не уважает каждого из своих предков, а если $$$c_i = 0$$$, то она их уважает.
Вы решили по очереди удалять из дерева вершины: на каждом шаге вы выбираете не корневую вершину, которая не уважает своего родителя, и которую не уважают все вершины, для которых она является родителем. Если таких вершин несколько, то вы выбираете вершину с минимальным номером. При удалении вершины $$$v$$$ все вершины, для которых $$$v$$$ была родителем, соединяются ребром с родителем $$$v$$$.
Пример удаления вершины $$$7$$$. Как только подходящих вершин для удаления нет, вы заканчиваете процесс. Выведите порядок, в котором вы удалите вершины. Обратите внимание, что этот порядок задается однозначно.
В первой строке содержится целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество вершин в дереве.
Далее в $$$n$$$ строках идёт идёт описание вершин дерева: в $$$i$$$-й строке находятся два целых числа $$$p_i$$$ и $$$c_i$$$ ($$$1 \le p_i \le n$$$, $$$0 \le c_i \le 1$$$), где $$$p_i$$$ — номер родителя вершины $$$i$$$, а $$$c_i = 0$$$, если вершина $$$i$$$ уважает своих предков, и $$$c_i = 1$$$, если вершина $$$i$$$ не уважает никого из своих предков. У корня дерева вместо номера предка записано число $$$-1$$$, для нее $$$c_i=0$$$. Гарантируется, что значения $$$p_i$$$ задают некоторое корневое дерево из $$$n$$$ вершин.
В случае, если вы удалите хотя бы одну вершину, в единственной строке через пробел выведите номера всех удаленных вершин в том порядке, в котором вы их удалите. В случае, если никого не нужно удалять, выведите единственное число $$$-1$$$.
5 3 1 1 1 -1 0 2 1 3 0
1 2 4
5 -1 0 1 1 1 1 2 0 3 0
-1
8 2 1 -1 0 1 0 1 1 1 1 4 0 5 1 7 0
5
Процесс удаления в первом примере будет происходить по следующему сценарию (см. картинку ниже, вершины с $$$c_i=1$$$ отмечены жёлтым):
- сначала будет удалена вершина $$$1$$$, так как она не уважает предков и все вершины, для которых она родитель (это одна вершина $$$2$$$) ее не уважают, а среди таких вершина номер $$$1$$$ — наименьший номер;
- вершина $$$2$$$ при этом будет соединена ребром с вершиной $$$3$$$;
- затем будет удалена вершина $$$2$$$, так как она не уважает предков, и все вершины, для которых она родитель (это одна вершина $$$4$$$) ее не уважают;
- при этом вершина $$$4$$$ будет соединена ребром с вершиной $$$3$$$;
- затем будет удалена вершина $$$4$$$, так как она не уважает предков, и все вершины, для которых она родитель (таких нет) ее не уважают (vacuous truth);
- из дерева будет удалена вершина $$$4$$$;
- процесс удаления завершается, так как нет подходящих вершин.
Во втором примере вершины не нужно удалять:
- у $$$2$$$ и $$$3$$$ есть вершины, для которых они являются родителями, но которые их уважают;
- $$$4$$$ и $$$5$$$ уважают руководство.
В третьем примере дерево будет меняться следующим образом:
