H. Циклы, кратные трём
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана последовательность $$$a_1,\dots,a_n$$$ длины $$$n$$$, изначально все её элементы — пустые. Над последовательностью совершают $$$n$$$ обновлений, в каждом из которых один из элементов $$$a$$$ становится некоторым числом, таким образом, что после всех обновлений $$$a$$$ становится перестановкой $$$1,2,\dots,n$$$.

После каждого обновления найдите число способов (по модулю $$$998\,244\,353$$$) заполнить остающиеся пустые места в $$$a$$$ так, чтобы $$$a$$$ стала перестановкой $$$1,2,\dots,n$$$, причём длины всех циклов в $$$a$$$ стали кратны $$$3$$$.

Перестановкой $$$1,2,\dots,n$$$ является последовательность длины $$$n$$$, состоящая из $$$n$$$ различных целых чисел от $$$1$$$ до $$$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$$$).

В $$$i$$$-й из следующих $$$n$$$ строк содержатся по два числа $$$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$$$ строк: число способов (по модулю $$$998\,244\,353$$$) после $$$1,2,\dots,n$$$ обновлений.

Примеры
Входные данные
6
3 2
1 4
4 5
2 6
5 1
6 3
Выходные данные
32
8
3
2
1
1
Входные данные
3
1 1
2 3
3 2
Выходные данные
0
0
0
Входные данные
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
Выходные данные
671571067
353924552
521242461
678960117
896896000
68992000
6272000
627200
62720
7840
1120
160
32
8
2
1
1
1
Примечание

В первом примере, скажем, после $$$3$$$-го обновления есть $$$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$$$.