Mạng truyền thông

Tổng công ty $Z$ gồm $N$ công ty con, đánh số từ $1$ tới $N$. Mỗi công ty con có một máy chủ. Để đảm bảo truyền tin giữa các công ty, $Z$ thuê $M$ đường truyền tin để kết nối $N$ máy chủ thành một mạng máy tính của Tổng công ty. Không có $2$ đường truyền nối cùng $1$ cặp máy chủ. Đường truyền $i$ nối máy chủ của $2$ công ty $u_i$, $v_i$ có chi phí là $w_i$. Mạng máy tính có tính thông suốt, nghĩa là từ một máy chủ có thể truyền tin đến một máy chủ bất kì khác bằng đường truyền trực tiếp hoặc qua nhiều đường trung gian.

Một đường truyền gọi là không tiềm năng nếu như: một mặt, việc loại bỏ đường truyền này không làm mất tính thông suốt; mặt khác, nó phải có tính không tiềm năng, nghĩa là không thuộc bất cứ mạng con thông suốt gồm $N$ máy chủ và $N-1$ đường truyền tin với tổng chi phí thuê bao nhỏ nhất nào của mạng máy tính.

Trong thời gian tới, chi phí thuê bao của một số đường truyền tin thay đổi. Tổng công ty muốn xác định với chi phí mới thì đường truyền thứ $k$ có là đường không tiềm năng hay không để xem xét chấm dứt việc thuê đường truyền này.

Dữ liệu vào

• Dòng đầu là $T$: số testcase. Tiếp theo là $T$ nhóm dòng, mỗi nhóm cho thông tin về một testcase.
• Dòng thứ nhất của mỗi nhóm gồm $3$ số nguyên dương $N$, $M$, $Q$ ($Q\le 30$).
• Dòng thứ $i$ trong $M$ dòng tiếp theo chứa $3$ số nguyên dương $u_i$, $v_i$, $w_i$ ($u_i\ne v_i$, $w_i<{10}^9$).
• Dòng thứ $j$ trong $Q$ dòng tiếp theo mô tả giả định thứ $j$:
  • Số đầu tiên là chỉ số $k_j$ của đường truyền tin cần xem xét.
  • Tiếp theo là $s_j$ ($s_j\le 100$) cho biết số lượng đường truyền có chi phí thuê mới.
  • Cuối cùng là $s_j$ cặp số nguyên dương $t_p$, $c_p$ cho biết đường truyền thứ $t_p$ có chi phí thuê mới là $c_p$ ($c_p<{10}^9$).

Các giả định độc lập với nhau: mỗi giả định chỉ thay đổi chi phí của các đường truyền được liệt kê trong nó, so với chi phí ban đầu. Các chỉ số $t_p$ trong một giả định đôi một khác nhau.

Dữ liệu ra

Gồm $T$ nhóm dòng, mỗi nhóm gồm $Q$ dòng. Mỗi dòng là câu trả lời cho giả định tương ứng trong input. Ghi YES nếu câu trả lời là khẳng định và NO trong trường hợp ngược lại.

Ràng buộc

• $1\le T\le 10$; trong một test, tổng các $N$ không vượt quá ${10}^5$ và tổng các $M$ không vượt quá ${10}^6$.
• $2\le N\le {10}^5$; $N-1\le M\le {10}^6$; mạng ban đầu thông suốt.
• $1\le Q\le 30$; $0\le s_j\le 100$; $1\le k_j,t_p\le M$.
• $1\le w_i,c_p<{10}^9$.

Subtasks

• Subtask 1 ($30\%$ số test): $N\le 100$.
• Subtask 2 ($30\%$ số test): $N\le {10}^4$ và $M\le {10}^5$.
• Subtask 3 ($40\%$ số test): $N\le {10}^5$ và $M\le {10}^6$.

Mỗi subtask gồm nhiều test, mỗi test được chấm điểm riêng.

Ví dụ