← 返回题目列表

Codeforces · 1053/E

E. 欧拉之旅

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

欧拉是一只可爱的小松鼠。秋天来临时,他会收集一些储备品过冬。有趣的是,欧拉喜欢以特定的方式收集橡子。一棵树可以被描述为 $$$n$$$ 个橡子,由 $$$n - 1$$$ 分支连接起来,这样每对橡子之间就只有一条路。让我们枚举从 $$$1$$$ 到 $$$n$$$ 的橡子。

松鼠选择一个橡子(编号为$$$1$$$的不一定)作为开始,并以一种称为“欧拉之旅”(见注释)的方式访问它们,并在最后一次访问时收集每个橡子。

今天早上凯特正在观察欧拉。她拿了一张纸,在他的路径上连续写下了橡子的索引。不幸的是,在她回家的路上开始下雨,一些数字变得难以辨认。现在这个女孩非常难过,因为她必须向老师陈述自己的观察结果。

“也许如果我猜出缺少的数字,我就能做到!”她想。帮助她恢复对某棵树的任何有效的欧拉游览,或者告诉她一定犯了一个错误。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$),表示树中橡子的数量。

第二行包含 $$$2n - 1$$$ 整数 $$$a_1, a_2, \ldots, a_{2n-1}$$$ ($$$0 \leq a_i \leq n$$$) — Kate 写下的树的欧拉环游。 $$$0$$$ 表示难以辨认的数字,必须猜测。

输出

如果没有满足给定描述的欧拉巡演,则在第一行输出“no”。

否则,在第一行输出“yes”,然后在第二行打印满足给定描述的欧拉之旅。

任何有效的欧拉游览都将被接受,因为老师不知道初始树到底是什么样子。

示例

输入 #1

2
1 0 0

输出 #1

yes
1 2 1

输入 #2

4
1 0 3 2 0 0 0

输出 #2

yes
1 4 3 2 3 4 1

输入 #3

5
0 1 2 3 4 1 0 0 0

输出 #3

no

注意

具有 $$$n$$$ 橡子的树的欧拉之旅是 $$$2n - 1$$$ 橡子索引的序列。这样每个橡子至少出现一次,第一个和最后一个橡子相同,并且每两个连续的橡子直接与一个分支连接。