← 返回题目列表

Codeforces · 901/A

A. 哈希树

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

Sasha 正在参加编程比赛。在其中一个问题中,她应该检查一些有根树是否同构。她以前从未见过这个问题,但是,作为一名经验丰富的参与者,她猜测她应该将树与某些序列匹配,然后比较这些序列而不是树。 Sasha 希望将每棵树与序列 a0, a1, ..., ah 相匹配,其中 h 是树的高度,ai 等于距离根 i 条边的顶点数。

不幸的是,这一次Sasha的直觉是错误的,可能有几棵树匹配相同的序列。为了展示这一点,您需要编写一个程序,在给定序列 ai 的情况下,构建两棵与该序列匹配的非同构有根树,或者确定只有一棵这样的树。

两棵有根树是同构的,如果您可以以这样的方式重新枚举第一棵树的顶点,使得根的索引变得等于第二棵树的根的索引,并且这两棵树变得相等。

有根树的高度是从根到任何其他顶点的路径上的最大边数。

输入

第一行包含一个整数 h (2 ≤ h ≤ 105) — 树的高度。

第二行包含 h + 1 个整数 — 序列 a0, a1, ..., ah (1 ≤ ai ≤ 2·105)。所有ai的总和不超过2·105。保证至少有一棵树匹配这个序列。

输出

如果只有一棵树匹配这个序列,则打印“perfect”。

否则在第一行打印“ambiguously”。在第二行和第三行中,按以下格式打印两棵树的描述:在一行中打印 $$\sum_{i=0}^{h} a_i$$ 整数,其中第 k 个应该是顶点 k 的父节点,或者等于 0(如果第 k 个顶点是根)。

这些树应该是非同构的并且应该匹配给定的序列。

示例

输入 #1

2
1 1 1

输出 #1

perfect

输入 #2

2
1 2 2

输出 #2

ambiguous
0 1 1 3 3
0 1 1 3 2

注意

第一个示例中唯一的树和第二个示例中的两棵打印树如图所示: