머리가 둘 달린 소

시간 제한2초메모리 제한512 MB

요약

N마리의 소가 각각 두 개의 머리를 가지고 있고, M쌍의 서로 싫어하는 머리는 서로 반대쪽 여물통을 향해야 한다. 각 덩어리가 유효한 배치를 가지도록 소를 최소 개수의 연속한 구간으로 나눈다.

난이도: 어려움10점 중 8점
유형: 그래프, 유니온 파인드, 투 포인터
정답자: 아직 제출이 없습니다

문제

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

(__)     (__)
(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$ 이하다. 한 줄에 주어진 두 머리는 서로 다르다. 같은 쌍이 여러 번 주어질 수도 있다.

출력

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

예제3

예제 1

입력

4 5
3 B 1 B
4 A 3 A
2 B 1 B
4 B 2 A
3 A 2 B

예상 출력

예제 2
입력
```
1 1
1 A 1 B
```
예상 출력
```
1
```
예제 3
입력
```
3 3
1 A 2 A
2 A 3 A
3 A 1 A
```
예상 출력
```
2
```