Lexicographically Smallest Path

Cho đồ thị vô hướng liên thô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ị có thể chứa khuyên (cạnh nối một đỉnh với chính nó) và đa cạnh.

Một hành trình từ đỉnh $a$ đến đỉnh $b$ là một dãy cạnh nối tiếp nhau đi từ $a$ tới $b$, trong đó được phép đi lại một đỉnh hoặc một cạnh nhiều lần. Ghép các ký tự trên các cạnh theo đúng thứ tự đi qua, ta được xâu ký tự của hành trình đó (hành trình rỗng cho xâu rỗng).

Gọi $f(a,b)$ là xâu nhỏ nhất theo thứ tự từ điển trong tất cả các xâu của mọi hành trình từ $a$ đến $b$. Lưu ý rằng số hành trình là vô hạn, nên xâu nhỏ nhất có thể không tồn tại: khi đó với mọi hành trình đều tìm được hành trình khác cho xâu nhỏ hơn thật sự.

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 $f(1,i)$ không tồn tại.

Nhắc lại thứ tự từ điển: xâu $x$ nhỏ hơn xâu $y$ nếu $x$ là tiền tố thật sự của $y$, hoặc tại vị trí khác nhau đầu tiên ký tự của $x$ nhỏ hơn ký tự của $y$.

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à tổng $M$ trên tất cả test case đều 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 $f(1,i)$ không tồn tại.

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\le 4\times {10}^5$, tổng $M\le 4\times {10}^5$

Ví dụ