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

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\le t\le 2·{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\le n\le 2·{10}^5$, $1\le m\le min(2·{10}^5,\frac{n(n-1)}{2})$).
  • $m$ dòng tiếp theo, dòng thứ $i$ gồm ba số $t_i$, $x_i$, $y_i$ ($t_i\in \{0,1\}$, $1\le x_i,y_i\le 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·{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ụ