Đếm số đường đi

Điểm: 7,00 (OI)

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

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

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Assembly, C#, C++, D, Dart, Go, Groovy, Java, Javascript, Kotlin, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Ruby, Rust, Scratch, Typescript, Zig

Cho một đồ thị có hướng $G$ gồm $n$ đỉnh, đánh số từ $1$ đến $n$ . Đồ thị có thể chứa vòng lặp (cạnh đi từ một đỉnh tới chính nó) nhưng không có cạnh bội — với mọi cặp đỉnh có thứ tự $(u, v)$ , có nhiều nhất một cạnh từ $u$ tới $v$ .

Một đường đi từ $u$ tới $v$ là một dãy cạnh sao cho:

Đỉnh $u$ là đầu của cạnh đầu tiên;
Đỉnh $v$ là cuối của cạnh cuối cùng;
Với mọi hai cạnh liền nhau, cạnh sau xuất phát từ đỉnh mà cạnh trước kết thúc.

Quy ước rằng dãy cạnh rỗng cũng là một đường đi từ $u$ tới $u$ .

Với mỗi đỉnh $v$ , hãy in ra một trong bốn giá trị:

$0$ — nếu không có đường đi nào từ $1$ tới $v$ ;
$1$ — nếu có đúng một đường đi từ $1$ tới $v$ ;
$2$ — nếu số đường đi từ $1$ tới $v$ là hữu hạn và lớn hơn $1$ ;
$- 1$ — nếu số đường đi từ $1$ tới $v$ là vô hạn.

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ ( $1 \leq t \leq 10^{4}$ ) — số bộ test.
Trước mỗi bộ test có một dòng trống.
Dòng đầu của mỗi bộ test chứa hai số nguyên $n$ và $m$ ( $1 \leq n \leq 4 \cdot 10^{5}$ , $0 \leq m \leq 4 \cdot 10^{5}$ ) — số đỉnh và số cạnh.
$m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_{i}, b_{i}$ ( $1 \leq a_{i}, b_{i} \leq n$ ) — cạnh có hướng từ $a_{i}$ tới $b_{i}$ .

Tổng $n$ qua tất cả bộ test không vượt quá $4 \cdot 10^{5}$ . Tổng $m$ qua tất cả bộ test không vượt quá $4 \cdot 10^{5}$ .

Dữ liệu ra

Với mỗi bộ test, in ra một dòng chứa $n$ số nguyên, mỗi số thuộc tập ${- 1, 0, 1, 2}$ — đáp án cho từng đỉnh từ $1$ tới $n$ .

Ràng buộc

$1 \leq t \leq 10^{4}$
$1 \leq n, m \leq 4 \cdot 10^{5}$ (theo nghĩa $1 \leq n$ và $0 \leq m$ , với tổng giới hạn $4 \cdot 10^{5}$ mỗi loại)
Đồ thị có thể chứa vòng lặp, nhưng không có cạnh bội.

Ví dụ

Input	Output	Giải thích
5 6 7 1 4 1 3 3 4 4 5 2 1 5 5 5 6 1 0 3 3 1 2 2 3 3 1 5 0 4 4 1 2 2 3 1 4 4 3	1 0 1 2 -1 -1 1 -1 -1 -1 1 0 0 0 0 1 1 2 1	Bộ test 1: tới đỉnh $1$ chỉ có đường đi rỗng; đỉnh $2$ không tới được; đỉnh $4$ có hai đường $[(1, 3), (3, 4)]$ và $[(1, 4)]$ ; đỉnh $5$ có vòng lặp $5 \to 5$ nên số đường đi vô hạn; đỉnh $6$ kéo theo cũng vô hạn. Bộ test 3: cả ba đỉnh nằm trên cùng một chu trình chứa đỉnh $1$ , nên có vô hạn đường đi tới mỗi đỉnh. Bộ test 5: tới đỉnh $3$ có hai đường khác nhau qua $2$ và qua $4$ .
1 1 1 1 1	-1	Đỉnh $1$ có vòng lặp tự nó, do đó có vô hạn đường đi (đi qua vòng lặp tùy ý lần).

Bình luận

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