소들의 프롬 나이트

$N$마리($2 \le N \le 10{,}000$)의 소들이 들떠 있다. 오늘은 프롬 나이트다. 소들은 가장 좋은 드레스를 입고 코사지와 새 신발을 갖춰 신었다. 오늘 밤 소들은 각자 라운드 댄스를 추려 한다.

라운드 댄스는 소만 출 수 있으며, 밧줄 묶음과 원형 물탱크가 필요하다. 소들은 물탱크 주위에 줄을 서서 시계 방향으로 1부터 $N$까지 차례대로 번호를 매긴다. 각 소는 물탱크를 바라보며 다른 댄서들이 보이도록 선다.

소들에게 총 $M$($2 \le M \le 50{,}000$)개의 밧줄이 배분된다. 각 밧줄은 그것을 발굽으로 쥐고 있는 소에게 주어진다. 각 소는 왼발과 오른발에 모두 밧줄을 하나 이상 받기를 바라며, 일부 소는 실망할 수 있다.

어떤 소(베시라고 하자)의 춤이 성공하려면 그녀가 쥔 밧줄이 제대로 배치되어 있어야 한다. 그녀 밧줄의 반대편 끝을 쥔 소들을 확인하고, 그 소들이 쥔 밧줄의 반대편 끝을 쥔 소들을 확인하고, 이런 식으로 이어서 확인한다. 베시가 시계 방향으로 춤추면, 같은 무리의 나머지 소들도 즉시 시계 방향으로 끌어당겨야 한다. 반시계 방향으로 춤추면 무리 전체를 반시계 방향으로 끌어당겨야 한다.

무리가 제대로 된 춤을 이루지 못하는 경우도 있다. 한 예로, 두 소를 잇는 밧줄이 하나뿐인 경우다. 한 소는 상대를 한 방향으로 끌 수 있어도 반대 방향으로는 끌 수 없다. 밀어내는 밧줄은 쓸모가 없기 때문이다. 소들은 발을 맞춰 춤을 춰야 한다. 결국 끌려가기만 하는 소가 있으면(밧줄을 하나만 쥐고 있을 수도 있다) 그 소는 나머지와 보조를 맞추지 못하므로 그 무리는 실격된다.

밧줄과 그 배분이 주어졌을 때, 라운드 댄스를 제대로 출 수 있는 소들의 무리는 몇 개인가? 소와 밧줄의 집합은 물탱크를 여러 번 감쌀 수 있다.

첫 번째 줄에 공백으로 구분된 정수 $N$과 $M$이 주어진다.

두 번째 줄부터 $M+1$번째 줄까지 각 줄에는 공백으로 구분된 정수 $A$와 $B$가 주어진다. 이는 시계 방향으로 소 $A$에서 소 $B$로 가는 밧줄을 뜻한다.

라운드 댄스를 성공적으로 출 수 있는 소들의 무리 수를 나타내는 정수 하나를 한 줄에 출력한다.