Thành phố nơi G ở có \(n\) địa điểm du lịch nổi tiếng và \(m\) con đường một chiều nối các điểm du lịch này. Con đường thứ \(i\) đi từ điểm du lịch \(u_i\) đến điểm du lịch \(v_i\).

Hiện tại, hệ thống giao thông đảm bảo rằng với mọi cặp điểm du lịch \(x, y\), luôn tồn tại một đường đi (có thể đi theo chiều mũi tên hoặc ngược chiều mũi tên) giữa chúng.

Mùa lễ hội sắp đến, thành phố muốn quy hoạch lại và chọn ra đúng \(n - 1\) trong số \(m\) con đường hiện có để xây dựng lại. Các con đường được chọn phải thỏa mãn tính chất sau:

• Có đúng \(1\) điểm du lịch không có con đường nào (trong số các đường được chọn) đi đến nó. Điểm này sẽ đóng vai trò là nơi bắt đầu tham quan.
• Tất cả các điểm du lịch còn lại, mỗi điểm có chính xác một con đường (trong số các đường được chọn) đi đến nó.

Hội đồng thành phố nhờ bạn kiểm tra xem có phương án nào thỏa mãn hay không. Nếu có, hãy chỉ ra một phương án cụ thể.

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) (\(1 \le T \le 3\)) là số bộ dữ liệu cần giải quyết.
• \(T\) nhóm dòng tiếp theo mô tả các bộ dữ liệu, mỗi nhóm có định dạng:
  • Dòng đầu tiên gồm hai số nguyên dương \(n, m\) (\(1 \le n \le 10^5\); \(n - 1 \le m \le 1.5 \cdot 10^5\)).
  • \(m\) dòng tiếp theo, mỗi dòng gồm hai số nguyên dương \(u_i, v_i\) (\(1 \le u_i, v_i \le n\); \(u_i \neq v_i\)) mô tả con đường thứ \(i\).

Output

• Với mỗi bộ dữ liệu, nếu không tìm được phương án thỏa mãn, in ra NO.
• Ngược lại, in ra YES trên dòng đầu tiên. Dòng tiếp theo in ra một xâu nhị phân độ dài \(m\):
  • Ký tự thứ \(i\) là 0: Con đường thứ \(i\) không được chọn.
  • Ký tự thứ \(i\) là 1: Con đường thứ \(i\) được chọn.
• Nếu có nhiều phương án, in ra một phương án bất kỳ.

Example

1
4 4
2 1
2 3
4 2
4 3

YES
1011

Scoring

• Subtask \(1\) (\(8\%\) số điểm): \(n = m \le 2000\).
• Subtask \(2\) (\(12\%\) số điểm): \(m \le 20\).
• Subtask \(3\) (\(12\%\) số điểm): \(n \le 20\).
• Subtask \(4\) (\(16\%\) số điểm): \(n \le 2000, m \le 4000\).
• Subtask \(5\) (\(24\%\) số điểm): \(u_i < v_i\) với mọi \(i\).
• Subtask \(6\) (\(28\%\) số điểm): không có ràng buộc gì thêm.