Memory Match

You are playing the game "Memory Match".

The game uses a set of $N$ picture cards. The cards come in pairs: there are $N/2$ different pictures, and each picture appears on exactly two cards.

At the start of the game the cards are shuffled and laid face down on the table. Players then take turns looking for two cards with the same picture. A turn consists of picking a face-down card and turning it over to reveal its picture, then picking another face-down card and turning that one over as well. If the two pictures are identical, both cards stay face up, the player scores one point and takes another turn. If the pictures differ, both cards are turned face down again and the turn passes to the next player.

It is now your turn. You are given a description of every action played in the game so far. Compute how many pairs you can score with certainty on this turn. Several card layouts may agree with everything observed so far, so report the largest number of pairs you are guaranteed to match in every one of those layouts.

Figure 1: A game with 8 cards. Only cards 3 and 6 have been matched and lie face up, and every other card is face down. How many pairs can you score?

The first line contains an even integer $N$, the number of cards on the table ($2 \le N \le 1000$).

The second line contains an integer $K$, the number of turns played so far ($0 \le K \le 1000$).

Each of the following $K$ lines describes one turn, in the order the turns were played. A line holds integers $C_1$ and $C_2$ followed by words $P_1$ and $P_2$. The numbers $C_1$ and $C_2$ are card positions on the table ($1 \le C_1, C_2 \le N$ and $C_1 \ne C_2$), and $P_1$ and $P_2$ are the pictures on the cards at those positions. Each word consists of between 1 and 20 lowercase letters a to z. If $P_1 = P_2$, the two cards stay face up and the positions $C_1$ and $C_2$ are never chosen again.

At least two cards are still face down.

Print one line with an integer $S$, the number of matching pairs you can score with certainty.