Description:
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$$$.
Input Format:
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.
Output Format:
Output $$$n$$$ lines: the number of ways (modulo $$$998\,244\,353$$$) after the first $$$1,2,\dots,n$$$ updates.
Note:
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$$$.