cho.sh

Two-Headed Cows

N cows each have two heads, and M dislike pairs require that those heads face opposite troughs. Split the cows into the fewest consecutive blocks that each admit a valid orientation.

Hard8GraphUnion-findTwo pointersNo attempts yetTime limit2sMemory limit512 MB

Problem

Farmer John wanted smarter cows, and he bred a cow with two heads. One head sits at the front of the cow and the other sits at the rear. The body is symmetric from front to back.

(__)     (__)
(oo)     (oo)
 \/-------\/
  ||     ||
  ||-----||
  ~~     ~~

That created a problem. The two heads on one cow, call them A and B, have completely different personalities. Head A of cow 1 might be friends with head A of cow 2 and still dislike head B of cow 2.

Every morning NN cows line up in order of their numbers, cow 1 at the front and cow NN at the back. Each cow has two heads, so John sets out two troughs side by side. One trough runs past the heads on one side, the other runs past the heads on the other side. John can turn any cow around. Turning a cow swaps the troughs its two heads face.

John wants to orient the cows so that no two heads that dislike each other eat from the same trough. Two heads that dislike each other must face opposite troughs.

For some inputs no orientation lets every cow eat at once, so John splits the feeding into several sessions. The cows fed in one session must have consecutive numbers. For example, session 1 feeds cows 1 to 10, session 2 feeds cows 11 to 14, and session 3 feeds cows 15 to 23. Within one session there must be an orientation where no two heads that dislike each other share a trough. Two heads that eat in different sessions may dislike each other freely.

You are given MM pairs of heads that dislike each other. Find the minimum number of feeding sessions John needs.

Input

The first line has NN and MM separated by a space. (1≤N≤250001 \le N \le 25000, 1≤M≤500001 \le M \le 50000)

Each of the next MM lines describes one pair of heads that dislike each other with four fields: a cow number, a head name, a cow number, and a head name. A head name is A or B. The line 4 A 37 B means head A of cow 4 dislikes head B of cow 37. Every cow number is between 1 and NN. The two heads on one line are different. The same pair may appear more than once.

Output

Print the minimum number of feeding sessions on the first line.