#P2022. 值班
值班
题目描述
所有的学科竞赛团队都拥有着自己的实验室,大家可以在实验室里学习、讨论、交流,然而该死的疫情又双叒叕开始了。为了安全考虑,实验室也加强了管理,只给每个团队一把钥匙用于开门,且要求疫情期间,实验室里的总人数不超过15人。为了保证同学们能够按时来到实验室,学长们决定制定一份值班表,以确保实验室随时都有人,便于大家能够利用它来学习(juan)。
学长们制定的值班方案如下:实验室里共有n名同学,分配到n个时间段到实验室值班,但有的同学有时候有课,不能在某个时间段来实验室值班。由于团队成员对实验室十分热爱,只有在万不得已的时候才不会到实验室。基于此,学长发现所有同学最多都只有1个时间段不能来实验室,且同一个时间段最多只有1名同学不能来。你能帮学长计算一下一共有多少种安排值班的方案数不呢?
输入格式
第1行输入n(1≤n≤15),m(1≤m≤n),分别表示实验室里的总人数和值班时间受限的要求数目(人员从1~n编号)
第2行到第m+1行,每行给出2个数字i,j分别表示编号为i的同学的值班受限时间段j(即第i名同学不能在第j个时间段来值班)
输出格式
输出方案的总数
样例
输入:
3 2
1 1
2 2
输出:
3
有以下3种排班方案:
2 1 3
2 3 1
3 1 2
Limitation
1s, 1024KiB for each test case.
Related
In following contests: