Định Hướng Các Liên Kết

Bạn cần hoàn thiện nhiều mạng liên kết độc lập. Trong mỗi mạng có $N$ đỉnh và $M$ liên kết. Một số liên kết đã có chiều cố định; những liên kết còn lại chưa được chọn chiều.

Hãy chọn chiều cho tất cả liên kết chưa định hướng sao cho sau cùng mọi liên kết đều có hướng và toàn bộ đồ thị không chứa chu trình có hướng. Chiều của một liên kết đã cố định không được thay đổi. Đồ thị ban đầu không nhất thiết liên thông.

Input

• Dòng đầu chứa số nguyên $T$ - số bộ dữ liệu độc lập.
• Với mỗi bộ dữ liệu:
• Dòng đầu chứa hai số nguyên $N$ và $M$.
• $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $t,x,y$:
  • $t=1$: liên kết đã có hướng từ $x$ đến $y$;
  • $t=0$: liên kết chưa định hướng nối $x$ với $y$.
• Trong một bộ dữ liệu không có self-loop và không có hai liên kết cùng nối một cặp đỉnh, bất kể thứ tự hai đầu mút.

Output

• Với mỗi bộ dữ liệu:
• Nếu không thể hoàn thành đồ thị như yêu cầu, in một dòng duy nhất:

NO

• Nếu có thể, in YES, sau đó in đúng $M$ dòng. Mỗi dòng gồm hai số nguyên $u$ $v$, biểu diễn một liên kết có hướng từ $u$ đến $v$ trong đồ thị hoàn chỉnh.

• Mỗi liên kết ban đầu phải xuất hiện đúng một lần trong $M$ dòng kết quả. Các liên kết đã có hướng phải giữ nguyên chiều. Thứ tự liệt kê các liên kết là tùy ý; nếu có nhiều cách định hướng hợp lệ, được phép in bất kỳ cách nào.

Constraints

• $1\le T\le 2\cdot 10^4$.
• $2\le N\le 2\cdot 10^5$ trong mỗi bộ dữ liệu.
• $1\le M\le \min (2\cdot 10^5,N(N-1)/2)$ trong mỗi bộ dữ liệu.
• $t\in \{0,1\}$.
• $1\le x,y\le N$ và $x\ne y$.
• Không có hai liên kết trùng cặp đầu mút trong cùng một bộ dữ liệu.
• Tổng $N$ trên toàn input không vượt quá $2\cdot 10^5$.
• Tổng $M$ trên toàn input không vượt quá $2\cdot 10^5$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $\sum N\le 100$ và $\sum M\le 200$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

1
5 6
1 4 2
0 1 2
1 3 4
0 5 3
0 1 5
1 4 5

YES
4 2
1 2
3 4
3 5
1 5
4 5

1
4 4
1 1 2
1 2 3
1 3 1
0 3 4

NO