ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > Kovrov IT 2007 > задача:


H. Two Captains

Задачи сборника

• A. Phalanx
• B. Bitsorting
• C. Cubes
• D. Factorial
• E. Lights
• F. Parliament
• G. Strange Numbers
• H. Two Captains
• I. Boundary Troops
• J. Wedding

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Павел Кузнецов, ПГУ. Сложность Гамма

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, YN. 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

Для отправки решений необходимо выполнить вход.

www.contester.ru