Table of Contents

## 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

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β€πβ€2β 1051β€nβ€2β 105; 0β€πβ€5β 1050β€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 2β 1052β 105 and the sum of all πm does not exceed 5β 1055β 105.

### The Number of Imposters solution codeforces

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

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

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.