CF599B.Spongebob and Joke

普及/提高-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

While Patrick was gone shopping, Spongebob decided to play a little trick on his friend. The naughty Sponge browsed through Patrick's personal stuff and found a sequence _a_1, _a_2, ..., a__m of length m, consisting of integers from 1 to n, not necessarily distinct. Then he picked some sequence _f_1, _f_2, ..., f__n of length n and for each number a__i got number b__i = f__a__i. To finish the prank he erased the initial sequence a__i.

It's hard to express how sad Patrick was when he returned home from shopping! We will just say that Spongebob immediately got really sorry about what he has done and he is now trying to restore the original sequence. Help him do this or determine that this is impossible.

当派特里克外出购物时,海绵宝宝决定对他的朋友开个小玩笑。顽皮的海绵宝宝翻看了派特里克的私人物品,发现了一个长度为 mm 的序列 a1, a2, …, ama_1,\ a_2,\ \dots,\ a_m,其中每个元素均为 11 到 nn 之间的整数(允许重复)。接着,他选取了一个长度为 nn 的序列 f1, f2, …, fnf_1,\ f_2,\ \dots,\ f_n,并对每个数 aia_i 计算出 bi=faib_i = f_{a_i}。最后,他擦除了原始序列 aia_i。

派特里克购物回家后感到多么悲伤,实在难以言表!我们只需说明:海绵宝宝立刻为自己所做之事深感愧疚,现在正努力恢复原始序列。请帮助他完成这一任务,或判断这是不可能的。

输入格式

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 100 000) — the lengths of sequences f__i and b__i respectively.

The second line contains n integers, determining sequence _f_1, _f_2, ..., f__n (1 ≤ f__i ≤ n).

The last line contains m integers, determining sequence _b_1, _b_2, ..., b__m (1 ≤ b__i ≤ n).

输入的第一行包含两个整数 nn 和 mm(1 ≤ n, m ≤ 100 0001 \leq n, m \leq 100\,000),分别表示序列 fif_i 和 bib_i 的长度。

第二行包含 nn 个整数,确定序列 f1, f2, …, fnf_1,\,f_2,\,\dots,\,f_n(1 ≤ fi ≤ n1 \leq f_i \leq n)。

最后一行包含 mm 个整数,确定序列 b1, b2, …, bmb_1,\,b_2,\,\dots,\,b_m(1 ≤ bi ≤ n1 \leq b_i \leq n)。

输出格式

Print "Possible" if there is exactly one sequence a__i, such that b__i = f__a__i for all i from 1 to m. Then print m integers _a_1, _a_2, ..., a__m.

If there are multiple suitable sequences a__i, print "Ambiguity".

If Spongebob has made a mistake in his calculations and no suitable sequence a__i exists, print "Impossible".

如果恰好存在一个序列 aia_i,使得对所有从 11 到 mm 的 ii 均满足 bi=faib_i = f_{a_i},则输出 "Possible",然后输出 mm 个整数 a1, a2, …, ama_1,\ a_2,\ \dots,\ a_m。

如果存在多个满足条件的序列 aia_i,则输出 "Ambiguity"。

如果海绵宝宝在计算中出错,即不存在任何满足条件的序列 aia_i,则输出 "Impossible"。

输入输出样例

  • 输入#1

    3 3
    3 2 1
    1 2 3

    输出#1

    Possible
    3 2 1
  • 输入#2

    3 3
    1 1 1
    1 1 1

    输出#2

    Ambiguity
  • 输入#3

    3 3
    1 2 1
    3 3 3

    输出#3

    Impossible

说明/提示

In the first sample 3 is replaced by 1 and vice versa, while 2 never changes. The answer exists and is unique.

In the second sample all numbers are replaced by 1, so it is impossible to unambiguously restore the original sequence.

In the third sample f__i ≠ 3 for all i, so no sequence a__i transforms into such b__i and we can say for sure that Spongebob has made a mistake.

在第一个样例中,3 被替换为 1,反之亦然,而 2 始终保持不变。答案存在且唯一。

在第二个样例中,所有数字均被替换为 1,因此无法明确还原原始序列。

在第三个样例中,对所有 ii 均有 fi≠3f_i \neq 3,因此不存在任何序列 aia_i 能变换为这样的 bib_i,我们可以确定海绵宝宝出错了。

输入解题思路,AI测评打分。不知道怎么写?

首页