문제

지안이에게는 $N$ ($1 \le N \le 2 \cdot 10^5$)개의 정점(번호 $1 \dots N$)과 $M$ ($N - 1 \le M \le 2 \cdot 10^5$)개의 간선으로 이루어진 무방향 그래프가 주어진다. 각 간선은 두 정점 $u, v$ ($1 \le u, v \le N$)와 해당 간선에 적힌 영어 소문자 $c$ (a..z)로 나타내어진다. 주어지는 그래프는 항상 연결 그래프이며, 중복 간선이나 셀프 루프가 존재할 수 있다.

정점 $a$에서 시작하여 $b$에서 끝나는 모든 경로에 대해, 경로에 포함된 간선의 문자를 순서대로 이어 붙여 만든 문자열 중 사전순으로 가장 작은 것을 $f(a, b)$라고 정의하자. 경로는 같은 간선을 여러 번 방문할 수 있다(즉, 사이클을 포함할 수 있다).

각 $i$ ($1 \le i \le N$)에 대해, 지안이를 도와 $f(1, i)$의 길이를 구하시오. 만약 그 길이가 유한하다면 길이를 출력하고, 무한히 길어질 수 있다면 $-1$을 출력한다.

입력

첫째 줄에 독립적인 테스트 케이스의 수 $T$ ($1 \le T \le 10$)가 주어진다. 각 테스트 케이스는 다음과 같은 형식으로 주어진다.

테스트 케이스의 첫째 줄에 정점의 수 $N$과 간선의 수 $M$이 공백으로 구분되어 주어진다.

다음 $M$개의 줄에는 두 정수 $u, v$와 소문자 알파벳 $c$가 공백으로 구분되어 주어진다.

모든 테스트 케이스에 대해 $N$의 총합과 $M$의 총합은 각각 $4 \cdot 10^5$을 초과하지 않음이 보장된다.

출력

각 테스트 케이스마다 $N$개의 정수를 한 줄에 공백으로 구분하여 출력한다.

예제 입력 1

2
1 0
2 2
1 1 a
2 1 b

예제 출력 1

0
0 -1

예제 입력 2

2
7 7
1 2 a
1 3 a
2 4 b
3 5 a
5 6 a
6 7 a
7 4 a
4 3
1 2 z
2 3 x
3 4 y

예제 출력 2

0 1 1 5 2 3 4
0 1 2 -1

점수

• 입력 3-4: 모든 간선의 문자가 a이다.
• 입력 5-8: 모든 간선의 문자가 a 또는 b이다.
• 입력 9-14: $N, M \le 5000$
• 입력 15-22: 추가 제약 조건이 없다.