# [Solution] The Number of Imposters solution codeforces

## The Number of Imposters solution codeforces

Theofanis started playing the new online game called “Among them”. However, he always plays with Cypriot players, and they all have the same name: “Andreas” (the most common name in Cyprus).

In each game, Theofanis plays with 𝑛n other players. Since they all have the same name, they are numbered from 11 to 𝑛n.

The players write 𝑚m comments in the chat. A comment has the structure of “𝑖i 𝑗j 𝑐c” where 𝑖i and 𝑗j are two distinct integers and 𝑐c is a string (1𝑖,𝑗𝑛1≤i,j≤n; 𝑖𝑗i≠j; 𝑐c is either imposter or crewmate). The comment means that player 𝑖i said that player 𝑗j has the role 𝑐c.

An imposter always lies, and a crewmate always tells the truth.

Help Theofanis find the maximum possible number of imposters among all the other Cypriot players, or determine that the comments contradict each other (see the notes for further explanation).

Note that each player has exactly one role: either imposter or crewmate.

### The Number of Imposters solution codeforces

Input

The first line contains a single integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases. Description of each test case follows.

The first line of each test case contains two integers 𝑛n and 𝑚m (1𝑛21051≤n≤2⋅105; 0𝑚51050≤m≤5⋅105) — the number of players except Theofanis and the number of comments.

Each of the next 𝑚m lines contains a comment made by the players of the structure “𝑖i 𝑗j 𝑐c” where 𝑖i and 𝑗j are two distinct integers and 𝑐c is a string (1𝑖,𝑗𝑛1≤i,j≤n; 𝑖𝑗i≠j; 𝑐c is either imposter or crewmate).

There can be multiple comments for the same pair of (𝑖,𝑗)(i,j).

It is guaranteed that the sum of all 𝑛n does not exceed 21052⋅105 and the sum of all 𝑚m does not exceed 51055⋅105.

### The Number of Imposters solution codeforces

Output

For each test case, print one integer — the maximum possible number of imposters. If the comments contradict each other, print 1−1.

### The Number of Imposters solution codeforces

Example

input

Copy
5
3 2
1 2 imposter
2 3 crewmate
5 4
1 3 crewmate
2 5 crewmate
2 4 imposter
3 4 imposter
2 2
1 2 imposter
2 1 crewmate
3 5
1 2 imposter
1 2 imposter
3 2 crewmate
3 2 crewmate
1 3 imposter
5 0


### The Number of Imposters solution codeforces

output

Copy
2
4
-1
2
5


### The Number of Imposters solution codeforces

Note

In the first test case, imposters can be Andreas 22 and 33.

In the second test case, imposters can be Andreas 11, 22, 33 and 55.

In the third test case, comments contradict each other. This is because player 11 says that player 22 is an imposter, and player 22 says that player 11 is a crewmate. If player 11 is a crewmate, then he must be telling the truth, so player 22 must be an imposter. But if player 22 is an imposter then he must be lying, so player 11 can’t be a crewmate. Contradiction.