Problem Statement

“宇宙虽有其起源，却没有终结——无限。
星球虽也有起源，却因其自身之力走向毁灭——有限。
拥有睿智之才是最为愚蠢者，历史上不胜枚举...
这也可以说是给那些抵抗者们的，神的最后通牒。”

Rintarou、Kurisu、Mayuri 在玩游戏。
有3种生物，小Rintarou、小Kurisu、和小Mayuri。
小Rintarou能战胜小Mayuri，小Kurisu能战胜小Rintarou，小Mayuri能战胜小 Kurisu

一共有\(n\)个笼子，编号为\(1\)到\(n\)，每个笼子里关了一个生物（上面三个之一），由于他们想让别人看到笼子里的生物，所以用布挡了起来，那么就假装笼子里的三种生物以相同的概率出现，即一共有\(3^n\)种可能的初始状态。

他们一共进行了\(m\)次操作。

操作有两种

1 u v 把第\(v\)个笼子拆掉，并把第\(v\)个笼子里的生物关到了第\(u\)个笼子里。两个生物在同一个笼子里会打架，胜者会活下来。如果种类相同则原来在\(u\)中的生物会活下来（主场优势，输的会被啊掉）

2 u Rintarou问Kurisu有多少种初始状态使得原来在第\(u\)个笼子里的生物现在还活着。

Kurisu觉得这道问题太水了不屑于做，于是把他交给了你。

Input Format

从标准输入读入数据。
第一行输入两个整数\(n,m\)，表示笼子的个数和操作个数。
接下来\(m\)行，每行描述了一个操作。
输入保证在所有第一种操作中，笼子\(u,v\)在对应的操作发生时都还没有被拆掉。

Output Format

向标准输出输出答案。
对于每一个第二种操作，输出一行一个整数，表示满足条件的初始状态数。答案可能很大，请对\(998244353\)取模后输出。

Sample 1

Input

3 5
2 1
1 2 1
2 1
1 2 3
2 1

Output

27
9
6

Constraints

对于所有测试数据，\(1 ≤ n ,m ≤ 2 × 10^5\)

对于前30% 的数据 \(n ,m ≤ 10\)
对于前50% 的数据 \(n ,m ≤ 3000\)
对于前100% 的数据 \(n ,m ≤ 200000\)