Bessie được cho một đồ thị vô hướng gồm \(N\) (\(1\le N\le 2 \cdot 10^5\)) đỉnh được đánh số \(1\dots N\) và \(M\) cạnh (\(N - 1\le M\le 2 \cdot 10^5\)). Mỗi cạnh được mô tả bởi hai số nguyên \(u, v\) (\(1\le u, v \le N\)), biểu thị một cạnh vô hướng giữa hai đỉnh \(u\) và \(v\), cùng một chữ cái Latin viết thường \(c\) trong khoảng từ a đến z, là giá trị trên cạnh. Đồ thị đã cho được đảm bảo liên thông. Đồ thị có thể có cạnh song song hoặc khuyên.

Định nghĩa \(f(a, b)\) là phép nối các giá trị cạnh nhỏ nhất theo thứ tự từ điển trong số tất cả các đường đi bắt đầu tại đỉnh \(a\) và kết thúc tại đỉnh \(b\). Một đường đi có thể chứa cùng một cạnh nhiều lần (tức là được phép có chu trình).

Với mỗi \(i\) (\(1\le i \le N\)), hãy giúp Bessie xác định độ dài của \(f(1, i)\). In ra độ dài này nếu nó hữu hạn; nếu không, in ra \(-1\).

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1\le T\le 10\)), số lượng bộ test độc lập. Mỗi bộ test có định dạng như sau:

Dòng đầu tiên chứa \(N\) và \(M\).

\(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên, sau đó là một chữ cái Latin viết thường.

Đảm bảo rằng cả tổng \(N\) lẫn tổng \(M\) trên tất cả các bộ test đều không vượt quá \(4\cdot 10^5\).

Dữ liệu ra

Với mỗi bộ test, in ra \(N\) số nguyên cách nhau bởi dấu cách trên một dòng mới.

Ví dụ

2
1 0
2 2
1 1 a
2 1 b

0
0 -1

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

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

Phân nhóm

• Các test 3–4: Mọi ký tự đều là a.
• Các test 5–8: Mọi ký tự đều là a hoặc b.
• Các test 9–14: \(N,M\le 5000\).
• Các test 15–22: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 2, Gold Division — Lexicographically Smallest Path. Tác giả: Daniel Zhu và Yash Belani.
https://usaco.org/index.php?page=viewproblem2&cpid=1570