Lexicographically Smallest Path

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

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 \leq i \leq 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 \leq T \leq 10$ ) - số test case.
Với mỗi test case:
- Dòng 1: Hai số nguyên $N$ và $M$ ( $1 \leq N \leq 2 \times 10^{5}$ , $N - 1 \leq M \leq 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 \leq T \leq 10$
$1 \leq N \leq 2 \times 10^{5}$
$N - 1 \leq M \leq 2 \times 10^{5}$
Tổng $N, M \leq 4 \times 10^{5}$

Ví dụ

Input	Output	Giải thích
2 1 0 2 2 1 1 a 2 1 b	0 0 -1	Test case 1: chỉ 1 đỉnh, f(1,1) = chuỗi rỗng, dài 0. Test case 2: đỉnh 1 có self-loop 'a', cạnh 1-2 nhãn 'b'. f(1,2): đi qua self-loop bao nhiêu lần cũng được thêm 'a' trước 'b', nên chuỗi nhỏ nhất dài vô hạn.
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	Test case 1: f(1,4) = "aaaaa" (dài 5), đi 1->3->5->6->7->4.

Bình luận

Không có bình luận tại thời điểm này.