Employees Dilemma :
Difficulty Level : Medium
Submissions : 379
Asked In :
Marks :15
: 12 | : 0
There are $$$N$$$ employees and $$$N$$$ chairs. You are given $$$M$$$ pair of integers $$$(X,Y)$$$ where $$$(X,Y)$$$ denotes that employee $$$X$$$ cannot sit on seat $$$Y$$$. You have to tell number of arrangements of $$$N$$$ employees on $$$N$$$ chairs such that all constraints satisfy.
The first line of input contains two space separated integers $$$N$$$ $$$(1 \le N \le 20)$$$ and $$$M$$$ $$$(0 \le M \le 100)$$$ — the number of employees (and the number of chairs) and the number of restrictions respectively.
The next $$$M$$$ lines contain two space separated integers $$$X$$$ and $$$Y$$$ $$$(1 \le X,Y \le N)$$$ each denoting that employee $$$X$$$ cannot sit on seat $$$Y$$$.
Print a single integer — the number of arrangements of the employees on the chairs such that all constraints satisfy.
3 1 2 2
4
20 0
2432902008176640000
In sample test case 1, the possible arrangements are $$${[2,1,3], [1,3,2], [3,1,2], [2,3,1]}$$$.
In sample test case 2, there are no restrictions. Hence there are $$$20!$$$ arrangements possible.
