Codeforces Round 332 (Div. 2) |
---|
Закончено |
Пока Патрик бегал по магазинам, Спанч Боб решил немного подшутить над своим другом. Порывшись в его вещах, проказник обнаружил последовательность a1, a2, ..., am длины m, составленную из целых чисел от 1 до n, не обязательно различных. Далее Спанч Боб придумал последовательность f1, f2, ..., fn длины n и получил для каждого числа ai число bi = fai. Исходную последовательность Спанч Боб, разумеется, стёр.
Сложно передать словами, как же расстроился Патрик когда вернулся из магазина! Скажем лишь, что Спанч Боб быстро пожалел о содеянном и пытается восстановить исходную последовательность. Помогите ему это сделать или определите, что это невозможно.
В первой строке входных данных находятся два целых числа n и m (1 ≤ n, m ≤ 100 000) — длины последовательностей fi и bi соответственно.
Во второй строке содержатся n целых чисел, определяющих последовательность f1, f2, ..., fn (1 ≤ fi ≤ n).
В последней строке записаны m целых чисел, определяющих последовательность b1, b2, ..., bm (1 ≤ bi ≤ n).
Если существует ровно одна последовательность ai, такая что bi = fai для всех i от 1 до m, то выведите "Possible". Далее выведите m целых чисел a1, a2, ..., am.
Если существует несколько подходящих последовательностей ai, то выведите "Ambiguity".
Если Спанч Боб ошибся в своих вычислениях, и ни одной подходящей последовательности ai не существует, то выведите "Impossible".
3 3
3 2 1
1 2 3
Possible
3 2 1
3 3
1 1 1
1 1 1
Ambiguity
3 3
1 2 1
3 3 3
Impossible
В первом примере 3 заменяется на 1 и наоборот, а 2 никогда не изменяется. Ответ существует, и он единствененный.
Во втором примере все числа заменяются на единицу, поэтому однозначно восстановить исходную последовательность невозможно.
В третьем примере fi ≠ 3 для всех i, поэтому никакая последовательность ai не перейдёт в такую bi и можно точно сказать, что Спанч Боб где-то ошибся.
Название |
---|