Теофанис начал играть в новую онлайн-игру под названием «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 (член экипажа).
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимально возможное количество предателей. Если комментарии противоречат друг другу, выведите \(-1\).
Примечание
В первом наборе входных данных, предателями могут быть Андреас \(2\) и Андреас \(3\).
Во втором наборе, предателями могут быть Андреас \(1\), Андреас \(2\), Андреас \(3\) и Андреас \(5\).
В третьем наборе, комментарии противоречат друг другу. Это потому что игрок \(1\) называет игрока \(2\) предателем, в то время как игрок \(2\) называет игрока \(1\) членом экипажа. Если игрок \(1\) — член экипажа, то он должен говорить правду, а значит игрок \(2\) — предатель. Но если игрок \(2\) — предатель, то он лжет, и, следовательно, игрок \(1\) не может быть членом экипажа. Противоречие.
Примеры
| № | Входные данные | Выходные данные |
|
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
|