Задача D. Нормальное честное списывание

Автор:И. Туфанов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

В группе школьников, состоящей из N человек (пронумерованных от 1 до N), распостранено списывание домашних заданий. Почерк большинства школьников неразборчив, поэтому для каждого школьника известен набор его товарищей, почерк которых он может разобрать.

Чтобы не делать лишнюю работу, школьники договорились, что домашние задания будет выполнять минимально необходимое число школьников. У них будут списывать те, кто понимает их почерк. И так далее, пока у всей группы не будет готовых домашних заданий.

Чтобы честно распределить работу, каждый день они выбирают другое множество выполняющих задание. Найдите максимальное количество дней, в течение которого этот уговор может действовать (т.е количество способов выбора школьников).

Формат входного файла

В первой строке входного файла содержатся числа N M. Далее следует M пар чисел в диапазаоне от 1 до N. Пара a b означает, что школьник с номером b может списать у школьника с номером a.

Формат выходного файла

Выходной файл должен содержать единственное целое число — количество способов. Ответ должен быть выведен без лидирующих нулей. В приведенном примере возможны три способа выбора школьников, удовлетворяющих условию: {1,5},{2,5},{3,5}. Школьник 4 списывает в любой ситуации.

Ограничения

1 ≤ N ≤ 104, 0 ≤ M ≤ 105

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5 4
1 2 
2 3
3 1
3 4
3

0.050s 0.013s 15