Cây Giáng sinh XOR

Cho một cây có $n$ đỉnh và $n-1$ cạnh. Mỗi cạnh được gắn một giá trị nguyên không âm $v$ với $0\le v<2^{30}$. Tuy nhiên, một số giá trị đã bị quên — với những cạnh đó, $v=-1$.

Có $m$ truy vấn. Truy vấn thứ $i$ gồm hai đỉnh $a_i$, $b_i$ và một bit chẵn lẻ $p_i\in \{0,1\}$. Gọi $X_i$ là XOR của tất cả các giá trị trên các cạnh thuộc đường đi đơn từ $a_i$ đến $b_i$. Khi đó, truy vấn yêu cầu số lượng bit $1$ trong biểu diễn nhị phân của $X_i$ có tính chẵn lẻ bằng $p_i$, nghĩa là $\text{popcount}(X_i)mod2=p_i$.

Hãy xác định xem có thể chọn giá trị cho các cạnh chưa biết (mỗi giá trị nằm trong $[0,2^{30})$) sao cho mọi truy vấn đều đúng hay không. Nếu có, in ra một cách gán hợp lệ; những cạnh đã biết phải giữ nguyên giá trị.

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ — số bộ test ($1\le t\le 2·{10}^4$). Mỗi bộ test có cấu trúc như sau:

• Dòng đầu chứa hai số $n$ và $m$ ($2\le n\le 2·{10}^5$; $1\le m\le 2·{10}^5$).
• $n-1$ dòng tiếp theo, mỗi dòng chứa ba số $x$, $y$, $v$ ($1\le x,y\le n$; $-1\le v<2^{30}$) mô tả một cạnh giữa đỉnh $x$ và $y$. Nếu $v=-1$ thì giá trị cạnh chưa biết; nếu $v\ge 0$ thì cạnh có giá trị $v$.
• $m$ dòng tiếp theo, mỗi dòng chứa ba số $a$, $b$, $p$ ($1\le a,b\le n$; $a\ne b$; $0\le p\le 1$).

Tổng $n$ trên tất cả các bộ test không vượt quá $2·{10}^5$. Tổng $m$ trên tất cả các bộ test cũng không vượt quá $2·{10}^5$. Các cạnh được đảm bảo tạo thành một cây.

Dữ liệu ra

Với mỗi bộ test:

• In YES nếu tồn tại cách gán hợp lệ, sau đó in $n-1$ dòng, mỗi dòng ba số $x$, $y$, $v$ ($0\le v<2^{30}$) — tập các cạnh phải trùng với đầu vào (xét không thứ tự), giá trị các cạnh đã biết phải giữ nguyên. Có thể in cạnh theo bất kì thứ tự nào.
• In NO nếu không tồn tại cách gán.

Nếu có nhiều đáp án, in ra bất cứ đáp án nào.

Ràng buộc

• $1\le t\le 2·{10}^4$
• $2\le n\le 2·{10}^5$, $1\le m\le 2·{10}^5$
• Tổng $n$ và tổng $m$ trên toàn bộ các bộ test đều không vượt quá $2·{10}^5$.
• $-1\le v<2^{30}$ cho cạnh; $0\le p\le 1$ cho truy vấn.

Ví dụ

Lưu ý: vì $\text{popcount}(x\oplus y)\equiv \text{popcount}(x)+\text{popcount}(y)\left(\mathrm{mod}2\right)$, chỉ duy nhất tính chẵn lẻ của mỗi cạnh là yếu tố quyết định. Bạn được tự do chọn giá trị cụ thể $0$ hoặc $1$ (hoặc bất cứ số nào có cùng chẵn lẻ) cho các cạnh chưa biết.