Định hướng các cạnh

Điểm: 7,00 (OI)

Giới hạn thời gian: 3.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

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho một đồ thị gồm $n$ đỉnh và $m$ cạnh. Đồ thị không nhất thiết liên thông. Một số cạnh đã được định hướng (không thể thay đổi), số còn lại là vô hướng và bạn cần chọn hướng cho chúng.

Hãy định hướng tất cả các cạnh vô hướng sao cho đồ thị thu được là đồ thị có hướng không chứa chu trình (DAG). Lưu ý rằng bạn không được thay đổi hướng của các cạnh đã có hướng và phải định hướng toàn bộ các cạnh vô hướng.

Có $t$ bộ dữ liệu độc lập cần xử lý.

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ ( $1 \leq t \leq 2 \cdot 10^{4}$ ) — số bộ dữ liệu.
Với mỗi bộ:
- Dòng đầu chứa hai số nguyên $n$ và $m$ ( $2 \leq n \leq 2 \cdot 10^{5}$ , $1 \leq m \leq min (2 \cdot 10^{5}, \frac{n (n - 1)}{2})$ ).
- m dòng tiếp theo, dòng thứ i gồm ba số ti, xi, yi (ti∈{0,1}, 1≤xi,yi≤n):
  - $t_{i} = 0$ : cạnh vô hướng nối $x_{i}$ và $y_{i}$ .
  - $t_{i} = 1$ : cạnh có hướng từ $x_{i}$ đến $y_{i}$ .

Đồ thị không có khuyên (cạnh nối một đỉnh với chính nó) và không có cạnh bội (với mỗi cặp $(x_{i}, y_{i})$ , không tồn tại cặp $(x_{i}, y_{i})$ hay $(y_{i}, x_{i})$ nào khác).

Đảm bảo tổng $n$ và tổng $m$ trên tất cả các bộ dữ liệu đều không vượt quá $2 \cdot 10^{5}$ .

Dữ liệu ra

Với mỗi bộ dữ liệu:

Nếu không thể định hướng để thu được DAG, in NO.
Ngược lại, in YES trên dòng đầu, sau đó in $m$ dòng mô tả các cạnh của đồ thị có hướng kết quả (thứ tự tùy ý). Hướng của các cạnh đã có hướng phải giữ nguyên. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ví dụ

Input	Output	Giải thích
1 3 1 1 2 3	YES 2 3	Chỉ có một cạnh có hướng từ 2 đến 3, giữ nguyên.
1 3 3 1 1 2 1 2 3 1 3 1	NO	Ba cạnh có hướng đã tạo thành chu trình $1 \to 2 \to 3 \to 1$ , không thể loại bỏ.
1 6 4 1 1 2 0 2 3 1 4 5 0 5 6	YES 1 2 3 2 4 5 6 5	Cạnh vô hướng (2,3) được định hướng $3 \to 2$ và (5,6) thành $6 \to 5$ ; đồ thị kết quả không có chu trình.

Bình luận

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