카드 짝 맞추기

"카드 짝 맞추기" 게임을 한다.

이 게임은 그림 카드 $N$장으로 진행한다. 카드는 짝을 이룬다. 서로 다른 그림이 $N/2$가지 있고, 각 그림은 정확히 두 장의 카드에 그려져 있다.

게임을 시작할 때 카드를 섞어 그림이 보이지 않게 뒤집어 놓는다. 참가자는 차례를 번갈아 가며 같은 그림의 카드 두 장을 찾는다. 한 차례에 뒤집혀 있는 카드 하나를 골라 뒤집어 그림을 확인하고, 다시 뒤집혀 있는 카드 하나를 더 골라 뒤집어 그림을 확인한다. 두 카드의 그림이 같으면 두 장은 그림이 보이는 상태로 남고, 고른 참가자는 1점을 얻은 뒤 한 차례를 더 진행한다. 두 카드의 그림이 다르면 두 장을 다시 뒤집어 놓고 차례는 다음 참가자에게 넘어간다.

이제 내 차례다. 지금까지 게임에서 일어난 모든 행동이 주어진다. 이번 차례에 확실하게 얻을 수 있는 점수를 구한다. 관찰한 기록과 모순되지 않는 카드 배치는 여러 가지일 수 있으므로, 그 모든 배치에서 반드시 맞출 수 있는 짝의 최대 개수를 구하면 된다.

그림 1: 카드 8장으로 진행 중인 상황. 3번과 6번 카드만 짝이 맞아 그림이 보이고, 나머지 카드는 모두 뒤집혀 있다. 이때 몇 짝을 확실하게 맞출 수 있을까?

첫째 줄에 테이블 위의 카드 수 $N$이 주어진다. $N$은 짝수다. ($2 \le N \le 1000$)

둘째 줄에 지금까지 진행된 차례의 수 $K$가 주어진다. ($0 \le K \le 1000$)

다음 $K$개 줄에는 각 차례를 진행된 순서대로 설명하는 정보가 주어진다. 한 줄은 정수 $C_1$, $C_2$와 단어 $P_1$, $P_2$로 이루어진다. $C_1$과 $C_2$는 테이블 위 카드의 위치이고 ($1 \le C_1, C_2 \le N$, $C_1 \ne C_2$), $P_1$과 $P_2$는 각각 그 위치의 카드에 그려진 그림이다. 각 단어는 알파벳 소문자 a부터 z까지로만 이루어지고, 길이는 1 이상 20 이하다. $P_1 = P_2$이면 두 카드는 그림이 보이는 상태로 남고, 위치 $C_1$과 $C_2$는 이후 다시 고를 수 없다.

뒤집혀 있는 카드는 항상 두 장 이상이다.

확실하게 맞출 수 있는 짝의 개수 $S$를 한 줄에 출력한다.