English · Original
Chinese · Translation
Formal · Original
Sasha is taking part in a programming competition. In one of the problems she should check if some rooted trees are isomorphic or not. She has never seen this problem before, but, being an experienced participant, she guessed that she should match trees to some sequences and then compare these sequences instead of trees. Sasha wants to match each tree with a sequence _a_0, _a_1, ..., _a__h_, where _h_ is the height of the tree, and _a__i_ equals to the number of vertices that are at distance of _i_ edges from root.
Unfortunately, this time Sasha's intuition was wrong, and there could be several trees matching the same sequence. To show it, you need to write a program that, given the sequence _a__i_, builds two non-isomorphic rooted trees that match that sequence, or determines that there is only one such tree.
Two rooted trees are isomorphic, if you can reenumerate the vertices of the first one in such a way, that the index of the root becomes equal the index of the root of the second tree, and these two trees become equal.
The height of a rooted tree is the maximum number of edges on a path from the root to any other vertex.
## Input
The first line contains a single integer _h_ (2 ≤ _h_ ≤ 105) — the height of the tree.
The second line contains _h_ + 1 integers — the sequence _a_0, _a_1, ..., _a__h_ (1 ≤ _a__i_ ≤ 2·105). The sum of all _a__i_ does not exceed 2·105. It is guaranteed that there is at least one tree matching this sequence.
## Output
If there is only one tree matching this sequence, print "_perfect_".
Otherwise print "_ambiguous_" in the first line. In the second and in the third line print descriptions of two trees in the following format: in one line print integers, the _k_\-th of them should be the parent of vertex _k_ or be equal to zero, if the _k_\-th vertex is the root.
These treese should be non-isomorphic and should match the given sequence.
[samples]
## Note
The only tree in the first example and the two printed trees from the second example are shown on the picture:
[{"iden":"statement","content":"Sasha 正在参加一场编程竞赛。在其中一个题目中，她需要判断一些有根树是否同构。她从未见过这个问题，但作为一名有经验的选手，她猜测应该将树映射为某种序列，然后比较这些序列而非直接比较树。Sasha 希望将每棵树映射为一个序列 #cf_span[a0, a1, ..., ah]，其中 #cf_span[h] 是树的高度，而 #cf_span[ai] 表示距离根节点恰好有 #cf_span[i] 条边的顶点数量。\n\n然而，这次 Sasha 的直觉是错误的，可能存在多个树对应同一个序列。为了证明这一点，你需要编写一个程序：给定序列 #cf_span[ai]，构造两个非同构的有根树，使其匹配该序列，或者判断仅存在唯一一棵这样的树。\n\n两个有根树同构，当且仅当可以重新编号第一棵树的顶点，使得根节点的编号与第二棵树的根节点编号相同，并且两棵树完全一致。\n\n有根树的高度定义为从根节点到任意其他顶点的路径中边数的最大值。\n\n第一行包含一个整数 #cf_span[h] (#cf_span[2 ≤ h ≤ 105]) —— 树的高度。\n\n第二行包含 #cf_span[h + 1] 个整数 —— 序列 #cf_span[a0, a1, ..., ah] (#cf_span[1 ≤ ai ≤ 2·105])。所有 #cf_span[ai] 的总和不超过 #cf_span[2·105]。保证至少存在一棵树匹配该序列。\n\n如果仅存在一棵匹配该序列的树，请输出 \"_perfect_\"。\n\n否则，在第一行输出 \"_ambiguous_\"。在第二行和第三行分别输出两棵树的描述，格式如下：每行输出 #cf_span[sum_{i=0}^{h} a_i] 个整数，第 #cf_span[k] 个整数表示顶点 #cf_span[k] 的父节点，若该顶点是根节点则为 0。\n\n这两棵树必须是非同构的，且均匹配给定的序列。"}},{"iden":"input","content":"第一行包含一个整数 #cf_span[h] (#cf_span[2 ≤ h ≤ 105]) —— 树的高度。第二行包含 #cf_span[h + 1] 个整数 —— 序列 #cf_span[a0, a1, ..., ah] (#cf_span[1 ≤ ai ≤ 2·105])。所有 #cf_span[ai] 的总和不超过 #cf_span[2·105]。保证至少存在一棵树匹配该序列。"},{"iden":"output","content":"如果仅存在一棵匹配该序列的树，请输出 \"_perfect_\"。否则，在第一行输出 \"_ambiguous_\"。在第二行和第三行分别输出两棵树的描述，格式如下：每行输出 #cf_span[sum_{i=0}^{h} a_i] 个整数，第 #cf_span[k] 个整数表示顶点 #cf_span[k] 的父节点，若该顶点是根节点则为 0。这两棵树必须是非同构的，且均匹配给定的序列。"},{"iden":"examples","content":"输入21 1 1输出perfect输入21 2 2输出ambiguous0 1 1 3 30 1 1 3 2"},{"iden":"note","content":"第一个示例中的唯一树，以及第二个示例中输出的两棵树如图所示："}]
**Definitions**
Let $ h \in \mathbb{Z} $ be the height of the tree.
Let $ A = (a_0, a_1, \dots, a_h) $ be a sequence of positive integers, where $ a_i $ denotes the number of vertices at distance $ i $ from the root.
**Constraints**
1. $ 2 \le h \le 10^5 $
2. $ 1 \le a_i \le 2 \cdot 10^5 $ for all $ i \in \{0, 1, \dots, h\} $
3. $ \sum_{i=0}^h a_i \le 2 \cdot 10^5 $
4. There exists at least one rooted tree matching $ A $.
**Objective**
Construct two non-isomorphic rooted trees with degree sequence $ A $, or output "perfect" if only one such tree exists.
A tree is defined by a parent array $ P = [p_1, p_2, \dots, p_n] $, where $ n = \sum_{i=0}^h a_i $, and $ p_k = 0 $ if vertex $ k $ is the root, otherwise $ p_k $ is the index of its parent.
The trees are isomorphic if there exists a bijection between their vertex sets preserving root and parent-child relationships.
**Decision Rule**
The tree is unique (output "perfect") if and only if $ a_i = 1 $ for all $ i \in \{1, 2, \dots, h-1\} $.
Otherwise (i.e., if $ \exists i \in \{1, 2, \dots, h-1\} $ such that $ a_i \ge 2 $), output "ambiguous" and construct two non-isomorphic trees:
- Tree 1: Each vertex at level $ i $ is connected to the first vertex at level $ i-1 $.
- Tree 2: At the first level $ i $ where $ a_i \ge 2 $, connect one vertex at level $ i $ to the first vertex at level $ i-1 $, and the rest to the second vertex at level $ i-1 $.
API Response (JSON)
{
"problem": {
"name": "C. Hashing Trees",
"description": {
"content": "Sasha is taking part in a programming competition. In one of the problems she should check if some rooted trees are isomorphic or not. She has never seen this problem before, but, being an experienced",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF902C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Sasha is taking part in a programming competition. In one of the problems she should check if some rooted trees are isomorphic or not. She has never seen this problem before, but, being an experienced...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"Sasha 正在参加一场编程竞赛。在其中一个题目中，她需要判断一些有根树是否同构。她从未见过这个问题，但作为一名有经验的选手，她猜测应该将树映射为某种序列，然后比较这些序列而非直接比较树。Sasha 希望将每棵树映射为一个序列 #cf_span[a0, a1, ..., ah]，其中 #cf_span[h] 是树的高度，而 #cf_s...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ h \\in \\mathbb{Z} $ be the height of the tree. \nLet $ A = (a_0, a_1, \\dots, a_h) $ be a sequence of positive integers, where $ a_i $ denotes the number of vertices at distance ...",
"is_translate": false,
"language": "Formal"
}
]
}