长度为 $$$n$$$ 的数组 $$$a_1,\dots,a_n$$$ 最初全为空白。有 $$$n$$$ 更新,其中 $$$a$$$ 的一个条目被更新为某个数字,使得 $$$a$$$ 在所有更新后变成 $$$1,2,\dots,n$$$ 的排列。
每次更新后,找出填充 $$$a$$$ 剩余空白条目的方法数(模 $$$998\,244\,353$$$),使 $$$a$$$ 成为 $$$1,2,\dots,n$$$ 的排列,并且 $$$a$$$ 中的所有循环长度都是 $$$3$$$ 的倍数。
$$$1,2,\dots,n$$$ 的排列是一个长度为 $$$n$$$ 的数组,由从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 个不同的整数以任意顺序组成。排列 $$$a$$$ 中的循环是成对不同整数 $$$(i_1,\dots,i_k)$$$ 的序列,使得 $$$i_2 = a_{i_1},i_3 = a_{i_2},\dots,i_k = a_{i_{k-1}},i_1 = a_{i_k}$$$。这个循环的长度是数字$$$k$$$,它是$$$3$$$的倍数当且仅当$$$k \equiv 0 \pmod 3$$$。
输入
第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 3 \cdot 10^5$$$, $$$n \equiv 0 \pmod 3$$$)。
接下来的$$$n$$$行的第$$$i$$$行包含两个整数$$$x_i$$$和$$$y_i$$$,表示第$$$i$$$更新将$$$a_{x_i}$$$更改为$$$y_i$$$。
保证 $$$x_1,\dots,x_n$$$ 和 $$$y_1,\dots,y_n$$$ 是 $$$1,2,\dots,n$$$ 的排列,即 $$$a$$$ 在所有更新后变成 $$$1,2,\dots,n$$$ 的排列。
输出
输出 $$$n$$$ 行:第一个 $$$1,2,\dots,n$$$ 更新后的路数(模 $$$998\,244\,353$$$)。
示例
输入 #1
6 3 2 1 4 4 5 2 6 5 1 6 3
输出 #1
32 8 3 2 1 1
输入 #2
3 1 1 2 3 3 2
输出 #2
0 0 0
输入 #3
18 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 1
输出 #3
671571067 353924552 521242461 678960117 896896000 68992000 6272000 627200 62720 7840 1120 160 32 8 2 1 1 1
注意
在第一个示例中,例如,在 $$$3$$$rd 更新后,$$$3$$$ 完成排列 $$$a = [4,\_,2,5,\_,\_]$$$ 的方法如下:
- $$$[4,1,2,5,6,3]$$$:唯一的循环是$$$(1\,4\,5\,6\,3\,2)$$$,长度为$$$6$$$。
- $$$[4,6,2,5,1,3]$$$:周期为 $$$(1\,4\,5)$$$ 和 $$$(2\,6\,3)$$$,长度为 $$$3$$$ 和 $$$3$$$。
- $$$[4,6,2,5,3,1]$$$:唯一的循环是$$$(1\,4\,5\,3\,2\,6)$$$,长度为$$$6$$$。
在第二个示例中,第一次更新创建了一个长度为 $$$1$$$ 的循环,因此无法使所有循环长度成为 $$$3$$$ 的倍数。