Hashing Trees

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"를 출력한다.

그렇지 않으면 첫 번째 줄에 "ambiguous"를 출력한다. 두 번째 줄과 세 번째 줄에는 다음 형식으로 트리 두 개의 설명을 출력한다. 각 줄에 개의 정수를 출력하며, 그중 k-th번째 정수는 정점 k의 부모여야 한다. 단, k-th번째 정점이 루트라면 영이어야 한다.

이 트리들은 서로 동형이 아니어야 하며 주어진 수열에 대응해야 한다.

첫 번째 예제의 유일한 트리와 두 번째 예제에서 출력된 두 트리는 그림에 나와 있다.