[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≀𝑛≀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

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.

The Number of Imposters solution codeforces


The Number of Imposters solution codeforcesYet another MEX problem solution codechefYet another MEX problem solution codechefYet another MEX problem solution codechef

Leave a Comment