H. Multiple of Three Cyclestime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputAn 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.InputThe 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.OutputOutput 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
NoteIn the first sample, for example, after the 3rd 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.
6
3 2
1 4
4 5
2 6
5 1
6 3

32 8 3 2 1 1 
['combinatorics', 'data structures', 'dp', 'dsu', 'math', '*3400']