bzoj#P3579. 破冰派对
破冰派对
题目描述
由于计算机系的同学们都很宅,很多同学虽然身在一个系,但是入学很久还是相互不认识。学生会主席小 Y 希望举办一次破冰派对,要让同学们多从寝室里走出来参加娱乐活动,也要让尽量多不认识的同学们通过活动相互认识。自然的,如果参加活动的同学互相都不认识,那便是极好的。:)
要办一次成功的派对是很不容易的,不光需要有同学参加,优秀的工作人员也是必不可少的。他们需要为派对的筹办付出很多的努力,因此一个和谐的团队是非常重要的。小 Y 希望所有工作人员都是相互认识的。
计算机系一共有 个同学,所有同学从 到 编号。有 对同学相互认识,而其余的同学相互不认识。小 Y 希望从中选出一些工作人员组成工作团队,让这个工作团队负责活动的组织,而其余的所有非工作人员,就自然都成为了活动的参与者。
小 Y 要求:
-
工作团队的成员必须相互认识;
-
参与活动的同学必须相互不认识;
-
至少有一个同学参与活动,也至少有一个同学是工作人员。
-
小 Y 想知道,一共有多少种工作团队的选择方案呢?
输入格式
第一行读入一个整数 ,表示测试数据的组数,接下来 组数据。
每组数据格式如下:
第一行包含两个整数 和 。
接下来 行,第 行包含两个不同的,在 到 之间的整数 ,表示编号为 和 的同学相互认识。
输入数据保证,在每一组测试数据中,任意两个同学之间的朋友关系都不会被列出两次。
输出格式
对于每一组测试数据输出一行一个整数,表示可行的方案总数,模 的余数。
2
1 0
4 4
1 2
1 3
2 3
3 4
0
3
数据规模与约定
对于 的数据满足 ,,。
题目来源
By 佚名提供