Aibohphobia
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a directed graph with $$$n$$$ vertices and $$$m$$$ edges. Each edge is labeled by a lowercase English letter.

A path in the graph is any sequence of edges [ e_1, e_2, ..., e_k ] such that the ending vertex of $$$e_i$$$ is the starting vertex of $$$e_{i+1}$$$ for every $$$1 \le i \lt k$$$. Vertices and edges may be visited multiple times.

Let the string written on a path be the string of length $$$k$$$ formed by the letters on its edges in order.

A path is called good if its string is not a palindrome.

Your task is to determine whether there exist arbitrarily long good paths. If yes, report that the answer is infinite. Otherwise, find the maximum possible length of a good path.

Recall that a string $$$s$$$ is a palindrome if it reads the same from left to right and from right to left.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the number of vertices and edges.

Each of the next $$$m$$$ lines contains two integers $$$u$$$, $$$v$$$ and a lowercase English letter $$$c$$$ ($$$1 \le u, v \le n$$$), describing a directed edge from vertex $$$u$$$ to vertex $$$v$$$ labeled by the letter $$$c$$$.

Multiple edges and self-loops are allowed.

Output

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the number of vertices and edges.

Each of the next $$$m$$$ lines contains two integers $$$u$$$, $$$v$$$ and a lowercase English letter $$$c$$$ ($$$1 \le u, v \le n$$$), describing a directed edge from vertex $$$u$$$ to vertex $$$v$$$ labeled by the letter $$$c$$$.

Multiple edges and self-loops are allowed.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

ПодзадачаБаллыДоп. ограниченияНеобх. подзадачи
14$$$n, m \le 5$$$—
27$$$n, m \le 20$$$, алфавит бинарный1
38$$$n, m \le 50$$$1
410$$$n, m \le 200$$$1–3
58либо $$$\mathrm{ans}$$$ нечётно, либо $$$\mathrm{ans}=0$$$, либо ответ равен $$$-1$$$1
614$$$n, m \le 3000$$$1–5
715$$$u_i \lt v_i$$$ для всех рёбер $$$(u_i, v_i)$$$3, 4, 6
814алфавит бинарный2, 4, 6
920нет дополнительных ограничений1–8

Examples

Input
1
1 1
1 1 a
Output
0
Input
1
4 3
1 2 a
2 3 b
3 4 c
Output
3
Input
1
5 4
1 2 a
2 3 b
3 4 b
4 5 a
Output
3
Input
1
2 2
1 2 b
2 2 a
Output
-1

Note

For each test case:

In case there exist good paths of arbitrarily large length print $$$-1$$$.

In case paths don't exist at all, print $$$0$$$.

Otherwise, print $$$x$$$, where $$$x$$$ is the maximum length of a good path.