베시에게 \(1\)번부터 \(N\)번까지 번호가 붙은 \(N\)개의 정점과 \(M\)개의 간선으로 이루어진 무방향 그래프가 주어진다. \((1 \le N \le 200,000,\ N-1 \le M \le 200,000)\)

각 간선은 두 정수 \(u,v\) \((1 \le u,v \le N)\)와 a부터 z까지의 소문자 \(c\)로 나타낸다. 이는 정점 \(u\)와 \(v\)를 잇는 무방향 간선의 값이 \(c\)임을 의미한다. 주어지는 그래프는 연결 그래프이다. 다중 간선과 셀프 루프가 존재할 수 있다.

정점 \(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\)의 합은 각각 \(400,000\) 이하이다.

출력

각 테스트 케이스마다 \(N\)개의 정수를 한 줄에 공백으로 구분하여 출력한다. \(i\)번째 정수는 \(f(1,i)\)의 길이가 유한하면 그 길이이고, 그렇지 않으면 \(-1\)이다.

예제 입력 1

2
1 0
2 2
1 1 a
2 1 b

예제 출력 1

0
0 -1

예제 설명 1

첫 번째 테스트 케이스에서 \(1\)번 정점은 간선을 지나지 않는 빈 경로로 도달할 수 있으므로 답은 \(0\)이다.

두 번째 테스트 케이스에서 \(2\)번 정점으로 가기 전에 값이 a인 셀프 루프를 원하는 만큼 반복할 수 있다. 이렇게 하면 사전순으로 계속 더 작은 문자열을 만들 수 있으므로 \(2\)번 정점에는 사전순으로 가장 작은 경로 문자열이 존재하지 않는다. 따라서 답은 \(-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

예제 설명 2

첫 번째 테스트 케이스에서 \(1\)번 정점의 답은 \(0\)이다. \(2\)번 정점과 \(3\)번 정점은 \(1\)번 정점과 인접하므로 답은 \(1\)이다. \(4\), \(5\), \(6\), \(7\)번 정점으로 가는 사전순 최소 경로는 \(2\)번 정점과 \(4\)번 정점 사이의 간선을 지나지 않음을 보일 수 있다.

두 번째 테스트 케이스에서 \(4\)번 정점 역시 문자열을 사전순으로 최소인 상태로 무한히 연장할 수 있으므로 사전순으로 가장 작은 경로 문자열이 존재하지 않는다. 따라서 답은 \(-1\)이다.

출처

USACO 2026 Second Contest, Gold, Problem 2. Lexicographically Smallest Path