머리가 둘 달린 소

농부 존은 더 똑똑한 소를 원했고, 머리가 둘 달린 소를 만드는 데 성공했다. 한 머리는 소의 앞쪽에 붙어 있고 다른 머리는 소의 뒤쪽에 붙어 있다. 소의 몸은 앞뒤로 대칭이다.

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

여기서 곤란한 일이 생겼다. 소 한 마리에 달린 두 머리는 성격이 완전히 다르다. 두 머리를 각각 A와 B라고 부르자. 1번 소의 A 머리가 2번 소의 A 머리와는 친해도 2번 소의 B 머리와는 사이가 나쁠 수 있다.

아침마다 소 $N$마리가 1번부터 $N$번까지 번호 순서대로 한 줄로 선다. 1번 소가 맨 앞이고 $N$번 소가 맨 뒤다. 소마다 머리가 둘이므로 존은 여물통 두 개를 나란히 놓는다. 한 여물통은 한쪽에 늘어선 머리 앞을 지나가고, 다른 여물통은 반대쪽에 늘어선 머리 앞을 지나간다. 존은 각 소를 앞뒤 어느 방향으로든 돌려 세울 수 있다. 소를 돌리면 그 소의 두 머리가 향하는 여물통이 서로 바뀐다.

존은 사이가 나쁜 두 머리가 같은 여물통에서 먹지 않도록 소의 방향을 정하려고 한다. 즉 서로 싫어하는 두 머리는 서로 다른 여물통을 향해야 한다.

방향을 어떻게 정해도 소 전체가 한 번에 같이 먹지 못하는 경우가 있다. 그래서 존은 밥을 여러 차례에 나누어 준다. 한 차례에 먹는 소는 번호가 연속해야 한다. 예를 들어 첫 차례에 1번부터 10번 소, 둘째 차례에 11번부터 14번 소, 셋째 차례에 15번부터 23번 소가 먹는 식이다. 한 차례 안에서는 사이가 나쁜 두 머리가 같은 여물통을 향하지 않도록 소의 방향을 정할 수 있어야 한다. 서로 다른 차례에 먹는 두 머리는 사이가 나빠도 상관없다.

사이가 나쁜 머리 쌍 $M$개가 주어진다. 존이 밥을 줘야 하는 최소 차례 수를 구하라.

첫째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다. ($1 \le N \le 25000$, $1 \le M \le 50000$)

다음 $M$개 줄에는 사이가 나쁜 머리 쌍이 한 줄에 하나씩 주어진다. 각 줄은 값 네 개로 이루어지고, 소 번호, 머리 이름, 소 번호, 머리 이름 순서다. 머리 이름은 A 또는 B다. 예를 들어 4 A 37 B는 4번 소의 A 머리와 37번 소의 B 머리가 서로 싫어한다는 뜻이다. 소 번호는 1 이상 $N$ 이하다. 한 줄에 주어진 두 머리는 서로 다르다. 같은 쌍이 여러 번 주어질 수도 있다.

첫째 줄에 존이 밥을 줘야 하는 최소 차례 수를 출력한다.