You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

所有的学科竞赛团队都拥有着自己的实验室，大家可以在实验室里学习、讨论、交流，然而该死的疫情又双叒叕开始了。为了安全考虑，实验室也加强了管理，只给每个团队一把钥匙用于开门，且要求疫情期间，实验室里的总人数不超过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.