В этой задаче Вам необходимо помочь Дмитрию Раисовичу Хусаинову получить хорошую оценку за четверть по математике. Беспощадный и злой учитель Дмитрия Раисовича, Леонид Иванович Лавринович, решил поиздеваться над ним и на последнем уроке сказал фразу следующего содержания: "Мы все понимаем, Дима, что ты самый умный, а мы все тупые. Вот и покажи, какой ты умный. Я задаю тебе 10 задач и до конца сегодняшнего дня ты должен принести ответы к этим задачам".

Так как недавно, все в классе Дмитрия Раисовича (кроме самого Дмитрия Раисовича), изучали комбинаторику, то Леонид Иванович, недолго думая, задал 10 задач приблизительно такого вида: "Задано натуральное число N. Пусть переменные X[1], X[2], ..., X[N] могут принимать произвольные натуральные значения от 1 до N, причем никакие две переменные не могут принимать одно и то же значение. Назовем набор значений переменных хорошим, если для любого i от 1 до K выполняются неравенства X[A[i]]<X[B[i]]. Числа K, A[1], A[2], ..., A[K], B[1], B[2], ..., B[k] также заданы. Найдите общее количество C хороших наборов".

Задание.

Итак, все задачи были одинаковыми и различались только значениями N, K, A[1], A[2], ..., A[k], B[1], B[2], ..., B[k]. Вам даны десять файлов, описывающих задачи, которые злой учитель задал Дмитрию Раисовичу, в формате, указанном ниже.

Входные данные.	Выходные данные.
N K A[1] B[1] A[2] B[2] ... A[K] B[K]	C

Пример.

0.in	0.out
4 4 1 2 2 4 1 3 3 4	2

Два хороших набора для задачи из файла 0.in следующие:

1) X[1]=1; X[2]=2; X[3]=3; X[4]=4;
2) X[1]=1; X[2]=3; X[3]=2; X[4]=4.

Ограничения.

5<=N<=20; 0<=K<=35