310514: CF1844H. Multiple of Three Cycles

H. Multiple of Three Cyclestime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

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

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

ExamplesInput

6
3 2
1 4
4 5
2 6
5 1
6 3

Output

32
8
3
2
1
1

Input

3
1 1
2 3
3 2

Output

0
0
0

Input

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

Output

671571067
353924552
521242461
678960117
896896000
68992000
6272000
627200
62720
7840
1120
160
32
8
2
1
1
1

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$.

题目大意：
给定一个长度为n的数组a，初始时所有元素为空。通过n次更新，每次更新数组a的一个条目，使得数组a变为1,2,...,n的一个排列。在每次更新后，求出将剩余的空条目填充为1,2,...,n的排列，并且使得a中所有循环的长度都是3的倍数的方法数（模998244353）。

输入数据格式：
第一行包含一个整数n（3≤n≤3×10^5，n是3的倍数）。
接下来n行，每行包含两个整数x_i和y_i，表示第i次更新将a_{x_i}更改为y_i。
保证x_1,...,x_n和y_1,...,y_n都是1,2,...,n的排列，即所有更新后a变为1,2,...,n的排列。

输出数据格式：
输出n行，分别表示每次更新后的方法数（模998244353）。

请注意，题目描述中的“循环”是指排列中的一种结构，其中每个元素指向下一个元素，形成一个闭环。例如，排列(1,4,5,6,3,2)中的循环是(1,4,5,6,3,2)，长度为6，是3的倍数。题目大意： 给定一个长度为n的数组a，初始时所有元素为空。通过n次更新，每次更新数组a的一个条目，使得数组a变为1,2,...,n的一个排列。在每次更新后，求出将剩余的空条目填充为1,2,...,n的排列，并且使得a中所有循环的长度都是3的倍数的方法数（模998244353）。 输入数据格式： 第一行包含一个整数n（3≤n≤3×10^5，n是3的倍数）。 接下来n行，每行包含两个整数x_i和y_i，表示第i次更新将a_{x_i}更改为y_i。 保证x_1,...,x_n和y_1,...,y_n都是1,2,...,n的排列，即所有更新后a变为1,2,...,n的排列。 输出数据格式： 输出n行，分别表示每次更新后的方法数（模998244353）。 请注意，题目描述中的“循环”是指排列中的一种结构，其中每个元素指向下一个元素，形成一个闭环。例如，排列(1,4,5,6,3,2)中的循环是(1,4,5,6,3,2)，长度为6，是3的倍数。