The Cow Prom

The $N$ ($2 \le N \le 10{,}000$) cows are excited: it is prom night! They wear their finest gowns, with corsages and new shoes. Tonight each cow will try to perform the Round Dance.

Only cows can perform the Round Dance, which needs a set of ropes and a circular stock tank. The cows line up around the tank and number themselves consecutively from 1 to $N$ in clockwise order. Each cow faces the tank so she can see the other dancers.

The cows receive a total of $M$ ($2 \le M \le 50{,}000$) ropes. Each rope is given to the cow who holds it in her hooves. Each cow hopes to hold one or more ropes in both her left and right hooves. Some cows may be disappointed.

For the dance to succeed for a cow (say, Bessie), the ropes she holds must be configured correctly. Check the cows at the other ends of her ropes, then the cows at the other ends of their ropes, and so on. When Bessie dances clockwise, she must instantly pull every other cow in her group clockwise too. If she dances counterclockwise, the entire group must be pulled counterclockwise.

A group can fail to form a proper dance. One case is when only one rope connects two cows. One cow can pull the other in one direction but cannot pull back, since pushing a rope does nothing. The cows must dance in lock-step. A dangling cow who is eventually pulled along, perhaps holding only one rope, disqualifies the group because she is not moving in step with the rest.

Given the ropes and who holds them, how many groups of cows can perform the Round Dance correctly? A set of ropes and cows may wrap around the tank many times.

Line 1: two space-separated integers $N$ and $M$.

Lines 2 to $M+1$: each line has two space-separated integers $A$ and $B$, describing a rope from cow $A$ to cow $B$ in the clockwise direction.

A single line with one integer: the number of groups of cows that can successfully perform the Round Dance.