AT_xmascon24_a Artistic Modulus
Description
$ 1 $ 個の入力ファイルにつき $ T $ 個のテストケースが与えられる．各テストケースで次のようなグラフ $ G $ が与えられるので，以下の問に答えよ．
$ G $ は $ N $ 頂点 $ M $ 辺の無向単純グラフである．頂点には $ 1, 2, \ldots, N $ と番号が付いている． $ i $ 番目 ( $ 1 \le i \le M $ ) の辺は頂点 $ A_i $ と頂点 $ B_i $ を結ぶ．
$ G $ の各頂点と各辺を**金色**と**銀色**のいずれかで塗る方法を考える (そのような塗り方は $ 2^{N+M} $ 通りある)．**芸術的な塗り方**とは，以下の条件をすべて満たす塗り方のこととする：
- 任意の**金色**の辺に対し，それが結ぶ頂点のうち少なくとも $ 1 $ つは**金色**である．
- 任意の**銀色**の頂点に対し，それに接続する辺のうち少なくとも $ 1 $ つは**銀色**である．
芸術的な塗り方の個数を $ 2 $ で割った余りを求めよ．
Input Format
標準入力の $ 1 $ 行目にテストケースの個数 $ T $ が与えられる．その後， $ T $ 個のテストケースがそれぞれ以下の形式で与えられる．
> $ N $ $ M $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_M $ $ B_M $
Output Format
各テストケースについて順番に $ 1 $ 行ずつ，芸術的な塗り方の個数を $ 2 $ で割った余りを出力せよ．
Explanation/Hint
### Sample Explanation 1
$ 1 $ 個目のテストケースでは，芸術的な塗り方は以下の図の $ 17 $ 通りである．
### Constraints
- $ 1 \le T \le 100 $ ．
- $ 0 \le N \le 2024 $ ．
- $ 0 \le M \le 2024 $ ．
- $ 1 \le A_i < B_i \le N $ ( $ 1 \le i \le M $ )．
- $ 1 \le i < j \le M $ のとき， $ (A_i, B_i) \ne (A_j, B_j) $ ．