Enter | Register
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP
PROBLEMS SUBMIT STATUS STANDINGS CUSTOM TEST
Order Capital Round 2
E. Permutation Commutation (Codeforces Round 1104, Div. 1 +
Div. 2)
time limit per test: 2 seconds
Finished
memory limit per test: 256 megabytes
Quack the Duck has a permutation∗ a of length n and an incomplete sequence b1 , b2 , … , bn . → Virtual participation
Each element of b is either −1 or an integer from 1 to n. Each integer from 1 to n appears at most once in b. Virtual contest is a way to take part in past
contest, as close as possible to participation
on time. It is supported only ICPC mode for
Quack hopes to complete b into a permutation that commutes with a. In other words, after replacing every −1 in b, the equality virtual contests. If you've seen these
ab = ba should hold for every 1 ≤ i ≤ n . problems, a virtual contest is not for you -
i i
solve these problems in the archive. If you
just want to solve some problem from a
Ja the Ghost wants to help Quack. Among all possible ways to complete b, he wants to find the lexicographically smallest† one. contest, a virtual contest is not for you -
solve this problem in the archive. Never use
Determine whether such a completion exists. If it exists, output the lexicographically smallest valid permutation b. Otherwise, someone else's code, read the tutorials or
communicate with other person during a
report that it is impossible. virtual contest.
∗
A permutation of length n is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2, 3, 1, 5, 4] is a permutation, but Start virtual contest
[1, 2, 2] is not a permutation (2 appears twice in the array), and [1, 3, 4] is also not a permutation (n = 3 but there is 4 in the array).
†
An array p is lexicographically smaller than an array q of the same size if and only if the following holds:
p ≠ q , and in the first position where p and q differ, the array p has a smaller element than the corresponding element in q. → Problem tags
Input data structures graphs greedy
Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10
4
). The description of the No tag edit access
test cases follows.
→ Contest materials
The first line of each test case contains an integer n (1
5
≤ n ≤ 2 ⋅ 10 ) — the length of the permutation.
The second line of each test case contains n integers a1 , a2 , … , an (1 ≤ ai ≤ n ) — the permutation a. Announcement (en)
Tutorial (en)
The third line of each test case contains n integers b1 , b2 , … , bn (bi = −1 or 1 ≤ bi ≤ n ) — the incomplete sequence b.
It is guaranteed that each integer from 1 to n appears at most once in b.
5
It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10 .
Output
For each test case, print "YES" if the answer exists, and "NO" otherwise.
You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be
recognized as positive responses.
If the answer exists, in the next line output n integers p1 , p2 , … , pn — the lexicographically smallest valid sequence after
replacing every −1 in b.
The sequence p must be a permutation, that is, each integer from 1 to n must appear exactly once in p. Also, it must satisfy
ap = pa for every 1 ≤ i ≤ n .
i i
Example
input Copy
12
3
2 3 1
-1 -1 -1
4
2 1 4 3
-1 -1 4 -1
4
2 1 4 3
3 1 -1 -1
4
2 1 4 3
1 -1 -1 2
5
2 3 1 5 4
2 -1 -1 -1 -1
5
2 3 1 5 4
4 -1 -1 -1 -1
6
2 3 1 5 6 4
4 -1 -1 -1 -1 -1
6
2 1 4 3 6 5
-1 3 -1 -1 -1 -1
6
3 5 6 2 1 4
-1 -1 -1 3 6 -1
7
2 3 1 5 4 6 7
-1 -1 -1 -1 -1 7 -1
8
2 3 4 1 6 7 8 5
5 7 -1 -1 -1 -1 -1 -1
8
2 3 4 1 6 7 8 5
5 -1 -1 -1 -1 -1 -1 -1
output Copy
YES
1 2 3
YES
1 2 4 3
NO
NO
YES
2 3 1 4 5
NO
YES
4 5 6 1 2 3
YES
4 3 1 2 5 6
NO
YES
1 2 3 4 5 7 6
NO
YES
5 6 7 8 1 2 3 4
Note
In the first test case, b = [1, 2, 3] commutes with any permutation a. Since all elements of b are unknown, this is also the
lexicographically smallest possible valid permutation.
In the second test case, a = [2, 1, 4, 3] and b3 = 4 . Since a3 = 4 , the condition for i = 3 gives ab 3
= ba
3
, so a4 = b4 ,
hence b4 = 3 . The remaining values are 1 and 2, and the lexicographically smallest valid choice is b1 = 1 , b2 = 2 . Thus the
answer is [1, 2, 4, 3] .
In the third test case, a = [2, 1, 4, 3], b1 = 3 , and b2 = 1 . For i = 1, the condition requires ab 1
= ba
1
. However,
ab = a3 = 4 , while ba = b2 = 1 . Since 4 ≠ 1, no valid completion exists.
1 1
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Jun/20/2026 14:15:33UTC-6 (h1).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions
Supported by