题目描述

由于计算机系的同学们都很宅，很多同学虽然身在一个系，但是入学很久还是相互不认识。学生会主席小 Y 希望举办一次破冰派对，要让同学们多从寝室里走出来参加娱乐活动，也要让尽量多不认识的同学们通过活动相互认识。自然的，如果参加活动的同学互相都不认识，那便是极好的。:)

要办一次成功的派对是很不容易的，不光需要有同学参加，优秀的工作人员也是必不可少的。他们需要为派对的筹办付出很多的努力，因此一个和谐的团队是非常重要的。小 Y 希望所有工作人员都是相互认识的。

计算机系一共有 $n$ 个同学，所有同学从 $1$ 到 $n$ 编号。有 $m$ 对同学相互认识，而其余的同学相互不认识。小 Y 希望从中选出一些工作人员组成工作团队，让这个工作团队负责活动的组织，而其余的所有非工作人员，就自然都成为了活动的参与者。

小 Y 要求：

1. 工作团队的成员必须相互认识；

2. 参与活动的同学必须相互不认识；

3. 至少有一个同学参与活动，也至少有一个同学是工作人员。

4. 小 Y 想知道，一共有多少种工作团队的选择方案呢？

输入格式

第一行读入一个整数 $T$，表示测试数据的组数，接下来 $T$ 组数据。

每组数据格式如下：
第一行包含两个整数 $n$ 和 $m$。
接下来 $m$ 行，第 $i$ 行包含两个不同的，在 $1$ 到 $n$ 之间的整数 $x_i,y_i$，表示编号为 $x_i$ 和 $y_i$ 的同学相互认识。

输入数据保证，在每一组测试数据中，任意两个同学之间的朋友关系都不会被列出两次。

输出格式

对于每一组测试数据输出一行一个整数，表示可行的方案总数，模 $10^6+3$ 的余数。

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

0
3

数据规模与约定

对于 $100\%$ 的数据满足 $1\le n\le 10^3$，$0\le m\le n^2$，$1\le T\le 6$。

题目来源

By 佚名提供