Вова утверждает, что придумал новую сортировку. Его сортировка отличается тем, что она может отсортировать, по мнению Вовы, любую перестановку длины N при этом делая одни и те же сравнения для любой перестановки. Всего она делает M сравнений, где i-е сравнение происходит над числами, находящимися на позициях xi и yi соответсвенно. Если на момент сравнения число находящееся на позиции xi оказывалось больше, то она меняет их местами.
Ваня скептически отнесся к открытию Вовы. Он уверен, что найдутся такие перестановки, которые Вовина сортировка не сможет упорядочить в порядке возрастания. Помогите Ване определить количество таких перестановок.
В первой строке задано два целых числа N и M — размер перестановки и количество сравнений в Вовиной сортировке.
В следующих M строках содержится описание сравнений. В i-й строке содержится два целых числа xi и yi — позиции сравниваемых элементов.
В единственной строке выведите одно целое число — количество перестановок, которые Вовина сортировка не сможет упорядочить в порядке возрастания.
3 3
1 2
2 3
1 3
2
2 1
1 2
0
2 1
2 1
2
В первом тестовом примере подходят следующие перестановки: [3, 2, 1], [2, 3, 1].
В третьем тестовом примере подходят следующие перестановки: [1, 2], [2, 1].
