← 返回题目列表

Codeforces · 1143/C

C. 女王

中文机器翻译题面 查看原题

给你一棵有根树,其顶点编号从 $$$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$$$。

示例

输入 #1

5
3 1
1 1
-1 0
2 1
3 0

输出 #1

1 2 4

输入 #2

5
-1 0
1 1
1 1
2 0
3 0

输出 #2

-1

输入 #3

8
2 1
-1 0
1 0
1 1
1 1
4 0
5 1
7 0

输出 #3

5

注意

第一个例子中的删除过程如下(见下图,$$$c_i=1$$$的顶点为黄色):

- 首先,您将删除顶点 $$$1$$$,因为它不尊重祖先,并且它的所有子节点(顶点 $$$2$$$)也不尊重它,并且 $$$1$$$ 是此类顶点中最小的索引;
- 删除后顶点$$$2$$$将与顶点$$$3$$$连接;
- 那么你将删除顶点$$$2$$$,因为它不尊重祖先,并且它的所有子节点(唯一的顶点$$$4$$$)也不尊重它;
- 顶点$$$4$$$将与顶点$$$3$$$连接;
- 那么你将删除顶点$$$4$$$,因为它不尊重祖先,并且它的所有孩子(没有)都不尊重它(空洞的事实);
- 您只需删除顶点$$$4$$$;
- 没有更多要删除的顶点。

在第二个示例中,您不需要删除任何顶点:

- 顶点 $$$2$$$ 和 $$$3$$$ 有尊重它们的子节点;
- 顶点 $$$4$$$ 和 $$$5$$$ 尊重祖先。

在第三个示例中,树将以这种方式更改: