D. Количество предателей
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Теофанис начал играть в новую онлайн-игру под названием «Among them». Однако, он постоянно играет с игроками из Кипра, и всех их зовут «Андреас» (самое распространенное имя на Кипре).

В каждой игре Теофанис играет с $$$n$$$ другими игроками. Так как у них всех одинаковые имена, то они были пронумерованы от $$$1$$$ по $$$n$$$.

Игроки написали $$$m$$$ комментариев в чате. Каждый комментарий имеет вид «$$$i$$$ $$$j$$$ $$$c$$$», где $$$i$$$ и $$$j$$$ — это два различных целых числа, а $$$c$$$ — строка ($$$1 \le i, j \le n$$$; $$$i \neq j$$$; $$$c$$$ — это либо imposter (предатель), либо crewmate (член экипажа)). Данный комментарий означает, что игрок $$$i$$$ говорит, что роль игрока $$$j$$$ — это $$$c$$$.

Предатели всегда врут, а члены экипажа всегда говорят правду.

Помогите Теофанису подсчитать максимальное возможное количество предателей среди всех кипрских игроков, или определить, что комментарии противоречат друг другу (ознакомьтесь с заметками для лучшего понимания).

Заметим, что у каждого игрока ровно одна роль: либо imposter (предатель), либо crewmate (член экипажа).

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

В первой строке каждого набора заданы два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$0 \le m \le 5 \cdot 10^5$$$) — количество игроков, исключая Теофаниса, и количество комментариев.

В каждой из следующих $$$m$$$ строк задан очередной комментарий игроков в форме «$$$i$$$ $$$j$$$ $$$c$$$», где $$$i$$$ и $$$j$$$ — это два различных целых числа, а $$$c$$$ — строка ($$$1 \le i, j \le n$$$; $$$i \neq j$$$; $$$c$$$ — это либо imposter, либо crewmate).

Для одной пары $$$(i, j)$$$ может быть более одного комментария.

Гарантируется, что сумма $$$n$$$ не превосходит $$$2 \cdot 10^5$$$ и сумма $$$m$$$ не превосходит $$$5 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимально возможное количество предателей. Если комментарии противоречат друг другу, выведите $$$-1$$$.

Пример
Входные данные
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
Выходные данные
2
4
-1
2
5
Примечание

В первом наборе входных данных, предателями могут быть Андреас $$$2$$$ и Андреас $$$3$$$.

Во втором наборе, предателями могут быть Андреас $$$1$$$, Андреас $$$2$$$, Андреас $$$3$$$ и Андреас $$$5$$$.

В третьем наборе, комментарии противоречат друг другу. Это потому что игрок $$$1$$$ называет игрока $$$2$$$ предателем, в то время как игрок $$$2$$$ называет игрока $$$1$$$ членом экипажа. Если игрок $$$1$$$ — член экипажа, то он должен говорить правду, а значит игрок $$$2$$$ — предатель. Но если игрок $$$2$$$ — предатель, то он лжет, и, следовательно, игрок $$$1$$$ не может быть членом экипажа. Противоречие.