CF1844H.Multiple of Three Cycles

An array $a_1,\dots,a_n$ of length $n$ is initially all blank. There are $n$ updates where one entry of $a$ is updated to some number, such that $a$ becomes a permutation of $1,2,\dots,n$ after all the updates.

After each update, find the number of ways (modulo $998\,244\,353$) to fill in the remaining blank entries of $a$ so that $a$ becomes a permutation of $1,2,\dots,n$ and all cycle lengths in $a$ are multiples of $3$.

A permutation of $1,2,\dots,n$ is an array of length $n$ consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. A cycle in a permutation $a$ is a sequence of pairwise distinct integers $(i_1,\dots,i_k)$ such that $i_2 = a_{i_1},i_3 = a_{i_2},\dots,i_k = a_{i_{k-1}},i_1 = a_{i_k}$. The length of this cycle is the number $k$, which is a multiple of $3$ if and only if $k \equiv 0 \pmod 3$.

一个长度为 $n$ 的数组 $a_1,\dots,a_n$ 初始时所有元素均为空。接下来进行 $n$ 次更新，每次将数组 $a$ 中的一个空位置赋值为某个整数，使得所有更新完成后，$a$ 成为 $1,2,\dots,n$ 的一个排列。

每次更新后，请计算：将 $a$ 中剩余的空位置填满，使得最终 $a$ 成为 $1,2,\dots,n$ 的一个排列，且 $a$ 中所有循环的长度均为 $3$ 的倍数的方案数（对 $998\,244\,353$ 取模）。

$1,2,\dots,n$ 的一个排列，是指由 $1$ 到 $n$ 中互不相同的 $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$；当且仅当 $k \equiv 0 \pmod 3$ 时，该长度是 $3$ 的倍数。

The first line contains a single integer $n$ ($3 \le n \le 3 \cdot 10^5$, $n \equiv 0 \pmod 3$).

The $i$-th of the next $n$ lines contains two integers $x_i$ and $y_i$, representing that the $i$-th update changes $a_{x_i}$ to $y_i$.

It is guaranteed that $x_1,\dots,x_n$ and $y_1,\dots,y_n$ are permutations of $1,2,\dots,n$, i.e. $a$ becomes a permutation of $1,2,\dots,n$ after all the updates.

第一行包含一个整数 $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$ 的一个排列。

Output $n$ lines: the number of ways (modulo $998\,244\,353$) after the first $1,2,\dots,n$ updates.

输出 $n$ 行：分别表示执行前 $1,2,\dots,n$ 次更新后，方案数对 $998\,244\,353$ 取模的结果。

In the first sample, for example, after the $3$rd update the $3$ ways to complete the permutation $a = [4,\_,2,5,\_,\_]$ are as follows:

• $[4,1,2,5,6,3]$: The only cycle is $(1\,4\,5\,6\,3\,2)$, with length $6$.
• $[4,6,2,5,1,3]$: The cycles are $(1\,4\,5)$ and $(2\,6\,3)$, with lengths $3$ and $3$.
• $[4,6,2,5,3,1]$: The only cycle is $(1\,4\,5\,3\,2\,6)$, with length $6$.

In the second sample, the first update creates a cycle of length $1$, so there are no ways to make all cycle lengths a multiple of $3$.

在第一个样例中，例如，在第 $3$ 次更新后，完成排列 $a = [4,\_,2,5,\_,\_]$ 的 $3$ 种方式如下：

• $[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$ 的倍数的方案。