Sinh viên lười (Lazy Student)

Cho một đồ thị vô hướng có trọng số gồm $n$ đỉnh và $m$ cạnh, không có khuyên và không có cạnh bội. Với mỗi cạnh, người ta cho biết trọng số $w_j$ của nó và một cờ $b_j\in \{0,1\}$ chỉ ra cạnh đó có thuộc một cây khung nhỏ nhất (MST) đã tìm được hay không ($b_j=1$ nếu thuộc, $b_j=0$ nếu không).

Tuy nhiên, danh sách các đỉnh đầu mút của các cạnh đã bị mất. Hãy phục dựng đồ thị: với mỗi cạnh $j$, hãy chỉ ra một cặp đỉnh $(u_j,v_j)$ sao cho:

• Đồ thị thu được liên thông, không có khuyên và không có cạnh bội.
• Tập các cạnh có $b_j=1$ tạo thành một cây khung nhỏ nhất của đồ thị (tổng trọng số của chúng đúng bằng trọng số của MST).

Nếu có nhiều cách phục dựng hợp lệ, in ra một cách bất kỳ. Nếu không tồn tại đồ thị nào thoả mãn, in ra $-1$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$ ($1\le n\le {10}^5$, $1\le m\le min({\displaystyle \frac{n(n-1)}{2}},{10}^5)$) — số đỉnh và số cạnh.
• $m$ dòng tiếp theo, dòng thứ $j$ chứa hai số nguyên $w_j$ và $b_j$ ($1\le w_j\le {10}^9$, $b_j\in \{0,1\}$).

Đảm bảo có đúng $n-1$ giá trị $b_j$ bằng $1$ và đúng $m-n+1$ giá trị $b_j$ bằng $0$.

Dữ liệu ra

• Nếu không tồn tại đồ thị thoả mãn, in ra $-1$.
• Ngược lại, in ra $m$ dòng. Dòng thứ $j$ chứa $u_j$ và $v_j$ ($1\le u_j,v_j\le n$, $u_j\ne v_j$) — hai đầu mút của cạnh thứ $j$ theo đúng thứ tự dữ liệu vào.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le m\le min({\displaystyle \frac{n(n-1)}{2}},{10}^5)$
• $1\le w_j\le {10}^9$, $b_j\in \{0,1\}$
• Có đúng $n-1$ cạnh $b_j=1$ và đúng $m-n+1$ cạnh $b_j=0$.

Ví dụ

Đáp án không duy nhất: bất kỳ cách phục dựng nào thoả mãn các điều kiện trên đều được chấp nhận.