Lexicographically Smallest Path

Bessie làm việc với đồ thị vô hướng gồm $N$ đỉnh và $M$ cạnh. Mỗi cạnh được gán một ký tự viết thường từ 'a' đến 'z'. Đồ thị liên thông và có thể có cạnh lặp hoặc đa cạnh.

Định nghĩa $f(a,b)$ là chuỗi nhỏ nhất theo thứ tự từ điển khi nối các ký tự trên cạnh dọc theo tất cả các đường đi từ đỉnh $a$ đến đỉnh $b$.

Với mỗi đỉnh $i$ ($1\le i\le N$), hãy xác định độ dài của $f(1,i)$. In $-1$ nếu độ dài là vô hạn.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $T$ ($1\le T\le 10$) - số test case.
• Với mỗi test case:
  • Dòng 1: Hai số nguyên $N$ và $M$ ($1\le N\le 2\times {10}^5$, $N-1\le M\le 2\times {10}^5$).
  • $M$ dòng tiếp theo: Mỗi dòng chứa hai số nguyên $u,v$ và một ký tự $c$ viết thường - biểu thị cạnh nối $u$ và $v$ với nhãn $c$.

Tổng $N$ và $M$ trên tất cả test case không vượt quá $4\times {10}^5$.

Dữ liệu ra

Với mỗi test case, in $N$ số nguyên cách nhau bởi dấu cách, số thứ $i$ là độ dài $f(1,i)$ hoặc $-1$ nếu vô hạn.

Ràng buộc

• $1\le T\le 10$
• $1\le N\le 2\times {10}^5$
• $N-1\le M\le 2\times {10}^5$
• Tổng $N,M\le 4\times {10}^5$

Ví dụ