解説

functionalグラフでかつ、 $p$ と $q$ はpermutationなので、 $p$ と $q$ は $(i , p[i]), (i, q[i])$ となる有向グラフを考えた時、シンプルなサイクルになることがわかる。

$i = p ^ {k} [i]$ となる $k$ を考えよう。

このとき、 $j = p ^ {k}[j]$ 、 $q[i] = j$ となる $j$ が必要なことがわかる

$j = p ^ {k / 2}[i]$ とすればよい

$x = p ^ {k}[x]$ となる $i$ の巡回サイクルとは別の $x$ をみつける(これがないときは作れないことが証明できる)

$j = x$ , $q[j] = p[i]$ として作ることができる

となり、以上で必要性を満たさないときは必ずつくれる

提出コード