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 → Virtual participation 
b1 , b2 , … , bn .
Virtual contest is a way to take part in past
Each element of b is either −1 or an integer from 1 to n. Each integer from 1 to n appears at contest, as close as possible to participation
on time. It is supported only ICPC mode for
most once in b. virtual contests. If you've seen these
problems, a virtual contest is not for you -
solve these problems in the archive. If you
Quack hopes to complete b into a permutation that commutes with a. In other words, after just want to solve some problem from a
replacing every −1 in b, the equality ab = ba should hold for every 1 ≤ i ≤ n .
i i
contest, a virtual contest is not for you -
solve this problem in the archive. Never use
someone else's code, read the tutorials or
Ja the Ghost wants to help Quack. Among all possible ways to complete b, he wants to find communicate with other person during a
the lexicographically smallest† one. virtual contest.

Determine whether such a completion exists. If it exists, output the lexicographically smallest Start virtual contest
valid permutation b. Otherwise, report that it is impossible.

A permutation of length n is an array consisting of n distinct integers from 1 to n in arbitrary order. For → Problem tags
∗

example, [2, 3, 1, 5, 4] is a permutation, but [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).
data structures graphs greedy
†
An array p is lexicographically smaller than an array q of the same size if and only if the following holds: No tag edit access

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.
→ Contest materials
Input
Announcement (en)
Each test contains multiple test cases. The first line contains the number of test cases t (
1 ≤ t ≤ 10
4
). The description of the test cases follows. Tutorial (en)

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.

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.

It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 105 .

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 = ba , so a4 = b4 , hence b4 = 3 . The remaining values are 1 and 2, and the

3 3

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 = ba . However, ab = a3 = 4 , while ba = b2 = 1 . Since 4 ≠ 1, no valid completion
1 1 1 1

exists.

Codeforces (c) Copyright 2010-2026 Mike Mirzayanov

The only programming contests Web 2.0 platform
Server time: Jun/23/2026 12:50:50UTC+5.5 (i1).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions

Supported by