28672번 - Кибер-взлом 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 3 | 3 | 3 | 100.000% |
문제
Ви пытается взломать сервера корпорации Арасака, чтобы отключить охрану и проникнуть в их офис. Искусственный интеллект сервера пытается ему в этом помешать.
Взлом происходит следующим образом. Рассмотрим ориентированный граф, на каждом ребре которого написана буква английского алфавита. Граф может содержать кратные ребра и даже петли. У Ви есть токен, изначально находящийся в некоторой вершине $v$, и у ИИ сервера есть токен, изначально находящийся в некоторой вершине $u$. Затем они по-очереди совершают ходы, Ви ходит первым. На своём ходу Ви выбирает произвольное ребро, исходящее из вершины, в которой находится его токен. Он перемещает токен по этому ребру, а также пытается произвести атаку типа $c$, где $c$ --- символ, написанный на выбранном ребре. ИИ на своём ходу также выбирает одно из рёбер, исходящих из вершины, в которой находится его токен, и перемещает токен по этому ребру. При этом, чтобы успешно отразить атаку, он должен выбрать ребро, на котором написан тот же символ $c$.
Если Ви не может сделать ход, потому что из вершины, в которой находится его токен, не исходит ни одного ребра, взлом завершается провалом. Если ИИ не может выбрать ребро, исходящее из вершины, в которой находится его токен, на котором написан символ $c$, взлом завершается успешно. Также, возможна ситуация, в которой Ви и ИИ будут делать ходы бесконечно долго.
Помогите Ви определить количество стартовых состояний, то есть пар вершин $v$ и $u$, при которых взлом будет произведен успешно при оптимальных действиях Ви и ИИ.
입력
В первой строке даны два целых числа $n$ и $m$ --- количество вершин и ребер в графе ($1 \le n \le 1\,000$, $0 \le m \le 1\,000$).
В следующих $m$ строках дано описание ребер графа. Каждая строка содержит два целых числа $a_i$ и $b_i$ и строчную букву английского алфавита $c_i$, они обозначают ребро из вершины $a_i$ в вершину $b_i$, на котором написан символ $c_i$ ($1 \le a_i, b_i \le n$).
출력
Выведите одно число --- искомое количество стартовых состояний.
예제 입력 1
3 3 1 2 a 2 3 b 3 1 c
예제 출력 1
6
예제 입력 2
5 10 2 2 c 3 5 b 5 4 b 2 3 b 3 5 c 3 1 b 4 2 a 4 4 a 2 4 b 2 5 c
예제 출력 2
15
노트
В первом примере, если изначально токены Ви и ИИ стоят в одной и той же вершине, процесс никогда не завершится. Во всех остальных случаях, взлом будет успешным.