8652: If You Can't Beat Them, Join Them!

Roundgod and kimoyami are playing the graph game 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:

1. Initially, there is a token on the source vertex s. Roundgod and kimoyami take turns moving the token through a directed edge, with Roundgod 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 10100 turns, then the game is considered a draw.

Roundgod is not an expert at this game and is often beaten by kimoyami. He remembered the famous quote, "If you can't beat them, join them!'', and then came up with the notion of join of graph games.
Given a nonempty collection of k(k>0) graph games (G1,s1),…,(Gk,sk). The join of the $k$ games is also a game with the following definition:

1. Roundgod and kimoyami take turns moving the tokens in all $k$ graph games simultaneously, with Roundgod going first. The game ends when either player cannot make a valid move in any of the kgames, and the player who cannot make a move loses. If the game lasts 10100 turns, then the game is considered a draw.

Now, given a collection of k graph games, (G1,s1),…,(Gk,sk), Roundgod then needs to choose a nonempty subset from the k games and play with kimoyami on the join of the chosen games. Roundgod 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 $(1\le T\le 5)$, denoting the number of test cases.

For each test case, the first line of the input contains an integer k(1≤k≤106), denoting the number of graph games in the collection.

Then the description of k graph games follows.

For the description of the $(1\le i\le k)$-th graph game, the first line contains three integers ni,mi,si(1≤ni,mi≤106,1≤si≤ni), denoting the number of vertices and edges of in the graph of the ith graph game, and the source vertex of the ith graph game, respectively.

Then mi lines follow, each line contains two integers u,v(1≤u,v≤ni,u!=v), denoting an edge in the graph of the ith graph game. Note that it is possible for the graph to have multiple edges, but not self loops.

It is guaranteed that for each test case, i=1∑kni≤2×106 and i=1∑kmi≤2×106

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