A boat which is certainly named "Beda" for some strange reasons happened
to have two captains. That could probably be quite acceptable, but the
two men don't get on very well as either of them thinks himself to be
more important than the other. Once they have to draw up all the sailors
in a row. Either of the two captains has his own view to the arrangement
of the sailors. After a brief argument one of them says to the other:
"Let me tell you which of the sailors should stand left of whom, and
then you will place them as you like, taking into account my request".
The second captain considered that a good idea as it gave them both
an opportunity to equally participate in the arrangement of the rows.
But he feared that the first captain could try to cheat and could put
forward too strict requirements that will leave no sufficient freedom
of choice. So, he is asking you now to make a program that will find
the number of arrangements of the sailors in the rows using the list
of the first captain's requirements.
Input
The first line of the input contains integers N and K
(1 ≤ N ≤ 18, 0 ≤ K). N is the number of
the sailors on board the ship (let all the sailors be numbered from
1 to N). K is the quantity of the first captain's
requirements. Then there should be K lines each having two
numbers X and Y. The requirement means that the sailor
numbered X must be to the left of the sailor numbered Y
in the row. It is provided that in each of the requirements 1 ≤ X,
Y ≤ N. And X is not equal to Y. No
requirement is given twice.
Output
Write one number which is the answer to the question.
|
Input 1
|
Output 1
|
4 2
2 1
4 3
|
6
|
Comment on the sample: There are 4 sailors on the
boat. Here are all the ways of arranging them:
2, 1, 4, 3
2, 4, 1, 3
2, 4, 3, 1
4, 2, 1, 3
4, 2, 3, 1
4, 3, 2, 1
|
