Ви пытается взломать сервера корпорации Арасака, чтобы отключить охрану и проникнуть в их офис. Искусственный интеллект сервера пытается ему в этом помешать.

Взлом происходит следующим образом. Рассмотрим ориентированный граф, на каждом ребре которого написана буква английского алфавита. Граф может содержать кратные ребра и даже петли. У Ви есть токен, изначально находящийся в некоторой вершине v, и у ИИ сервера есть токен, изначально находящийся в некоторой вершине u. Затем они по очереди совершают ходы, Ви ходит первым. На своём ходу Ви выбирает произвольное ребро, исходящее из вершины, в которой находится его токен. Он перемещает токен по этому ребру, а также пытается произвести атаку типа c, где c символ, написанный на выбранном ребре. ИИ на своём ходу также выбирает одно из рёбер, исходящих из вершины, в которой находится его токен, и перемещает токен по этому ребру. При этом, чтобы успешно отразить атаку, он должен выбрать ребро, на котором написан тот же символ c.

Если Ви не может сделать ход, потому что из вершины, в которой находится его токен, не исходит ни одного ребра, взлом завершается провалом. Если ИИ не может выбрать ребро, исходящее из вершины, в которой находится его токен, на котором написан символ c, взлом завершается успешно. Также, возможна ситуация, в которой Ви и ИИ будут делать ходы бесконечно долго.

Помогите Ви определить количество стартовых состояний, то есть пар вершин v и u, при которых взлом будет произведен успешно при оптимальных действиях Ви и ИИ.

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

В первой строке даны два целых числа n и m (1 ≤ n ≤ 1000, 0 ≤ m ≤ 1000) - количество вершин и ребер в графе.

В следующих m строках дано описание ребер графа. Каждая строка содержит два целых числа ai и bi и строчную букву английского алфавита ci, они обозначают ребро из вершины ai в вершину bi, на котором написан символ ci (1 ≤ ai, bi ≤ n).

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

Выведите одно число - искомое количество стартовых состояний.

Замечание

В первом примере, если изначально токены Ви и ИИ стоят в одной и той же вершине, процесс никогда не завершится. Во всех остальных случаях, взлом будет успешным.