If You Can't Beat Them, Join Them!

<tt>Roundgod</tt> and <tt>kimoyami</tt> are playing the <strong>graph game</strong> on a directed graph.
Given a directed graph $G=(V,E)$ and a source vertex $s\in V$, the graph game $(G,s)$ is defined as follows:
<ol>
<li> Initially, there is a token on the source vertex $s$. <tt>Roundgod</tt> and <tt>kimoyami</tt> take turns moving the token through a directed edge, with <tt>Roundgod</tt> going first. The game ends when either player cannot make a valid move, and the player who cannot make a move loses. If the game lasts $10^{100}$ turns, then the game is considered a draw. </li>
</ol>

<tt>Roundgod</tt> is not an expert at this game and is often beaten by <tt>kimoyami</tt>. He remembered the famous quote, "If you can't beat them, join them!'', and then came up with the notion of <strong>join of graph games</strong>.
Given a nonempty collection of $k(k>0)$ graph games $(G_1,s_1),\dots,(G_k,s_k)$. The <strong>join</strong> of the $k$ games is also a game with the following definition:
<ol>
<li> <tt>Roundgod</tt> and <tt>kimoyami</tt> take turns moving the tokens in all $k$ graph games <strong>simultaneously</strong>, with <tt>Roundgod</tt> going first. The game ends when either player cannot make a valid move <strong>in any of the $k$ games</strong>, and the player who cannot make a move loses. If the game lasts $10^{100}$ turns, then the game is considered a draw. </li>
</ol>

Now, given a collection of $k$ graph games, $(G_1,s_1),\dots,(G_k,s_k)$, <tt>Roundgod</tt> then needs to choose a <strong>nonempty subset</strong> from the $k$ games and play with <tt>kimoyami</tt> on the <strong>join</strong> of the chosen games. <tt>Roundgod</tt> wonders, how many ways are there to choose such a nonempty subset so that he may win the game under the optimal strategy of both players? As the answer may be too large, you need to output the answer modulo $998244353$.

The first line contains an integer $T(1\leq T\leq 5)$, denoting the number of test cases.

For each test case, the first line of the input contains an integer $k(1\leq k\leq 10^6)$, denoting the number of graph games in the collection.

Then the description of $k$ graph games follows.

For the description of the $i(1\leq i\leq k)$-th graph game, the first line contains three integers $n_i,m_i,s_i(1\leq n_i,m_i\leq 10^6,1\leq s_i\leq n_i)$, denoting the number of vertices and edges of in the graph of the $i$th graph game, and the source vertex of the $i$th graph game, respectively.

Then $m_i$ lines follow, each line contains two integers $u,v(1\leq u,v\leq n_i,u\neq v)$, denoting an edge in the graph of the $i$th graph game. Note that it is possible for the graph to have <strong>multiple edges</strong>, but not <strong>self loops</strong>.

It is guaranteed that <strong>for each test case</strong>, $\sum\limits_{i=1}^{k}n_i\leq 2\times 10^6$ and $\sum\limits_{i=1}^{k}m_i\leq 2\times 10^6$

Output an integer in a line, denoting the answer taken modulo $998244353$.

2
1
4 3 1
1 2
1 3
3 4
3
2 2 1
1 2
2 1
2 1 1
1 2
2 1 2
1 2

1
2

2022“杭电杯”中国大学生算法设计超级联赛（9）