사이버 해킹

Ви는 아라사카 기업의 서버를 해킹해 경비 시스템을 끄고 사무실에 침입하려 합니다. 서버의 인공지능은 이를 막으려 합니다.

해킹은 다음과 같이 진행됩니다. 각 간선에 영문 소문자가 적혀 있는 방향 그래프를 생각합시다. 그래프에는 다중 간선과 자기 루프가 있을 수 있습니다. Ви는 정점 $v$에 놓인 토큰을 가지고 있고, 서버의 AI는 정점 $u$에 놓인 토큰을 가지고 있습니다. 두 플레이어는 번갈아 움직이며, Ви가 먼저 시작합니다.

자신의 차례에 Ви는 토큰이 있는 정점에서 나가는 간선 하나를 고릅니다. 토큰을 그 간선을 따라 옮기고, 간선에 적힌 문자 $c$로 $c$형 공격을 시도합니다. AI도 자신의 차례에 토큰이 있는 정점에서 나가는 간선 하나를 고르고 토큰을 옮깁니다. 공격을 막으려면 AI는 같은 문자 $c$가 적힌 간선을 골라야 합니다.

Ви가 움직일 수 없는 경우, 즉 토큰이 있는 정점에서 나가는 간선이 하나도 없으면 해킹은 실패로 끝납니다. AI가 토큰이 있는 정점에서 나가는 간선 중 문자 $c$가 적힌 간선을 고를 수 없으면 해킹은 성공으로 끝납니다. 두 플레이어가 무한히 움직이는 경우도 있을 수 있습니다.

Ви와 AI가 최적으로 행동할 때 해킹이 성공하는 시작 상태의 개수를 구하세요. 시작 상태는 정점 쌍 $(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$).

시작 상태의 개수를 한 개의 정수로 출력하세요.

첫 번째 예제에서 Ви와 AI의 토큰이 같은 정점에서 시작하면 과정이 끝나지 않습니다. 그 밖의 모든 경우에 해킹은 성공합니다.