Cải thiện đánh giá

Quốc gia $Beta$ có $N$ thành phố được đánh số từ $1$ đến $N$. Các thành phố được nối với nhau bởi $M$ con đường hai chiều, được đánh số từ $1$ đến $M$, giữa hai thành phố bất kỳ có tối đa một con đường nối trực tiếp chúng. Con đường hai chiều số $i$ $(1\le i\le M)$ nối trực tiếp giữa hai thành phố phân biệt $U_i$ và $V_i$ có độ dài $W_i$. Một đường đi gồm $K$ thành phố từ thành phố $X$ tới thành phố $Y$ là một chuỗi các thành phố $P_1,P_2,\dots ,P_K$ sao cho $P_1=X$, $P_K=Y$ và có con đường trực tiếp giữa hai thành phố $P_i$ và $P_{i+1}$ $(\forall i=1,2,\dots ,K-1)$. Ở quốc gia $Beta$, mọi thành phố đều có đường đi tới thành phố khác.

Chi phí di chuyển của một đường đi từ $X$ tới thành phố $Y$ là tổng độ dài của các con đường trên đường đi đó. Gọi $D(X,Y)$ là chi phí di chuyển nhỏ nhất trong số các chi phí di chuyển của các đường đi từ thành phố $X$ tới thành phố $Y$. Quy ước $D(X,X)=0$ với mọi thành phố $X$.

Thành phố số $1$ có một nhà máy đúc khuôn và thành phố số $2$ có một nhà máy sản xuất mạ tĩnh điện. Một doanh nghiệp muốn chọn một thành phố nào đó để mở một trung tâm chế tạo thép trang trí sử dụng nguyên liệu từ nhà máy đúc khuôn và nhà máy sản xuất mạ tĩnh điện. Thành phố $Y$ được gọi là tốt hơn hoặc tương đương với thành phố $X$ khi và chỉ khi $D(Y,1)\le D(X,1)$ và $D(Y,2)\le D(X,2)$. Lưu ý, thành phố $X$ được xem là tốt hơn hoặc tương đương so với chính nó. Doanh nghiệp tính hạng của thành phố $X$ là số lượng thành phố $Y$ tốt hơn hoặc tương đương so với thành phố $X$. Cụ thể, công thức tính hạng là:

$$R(X)=|\{Y\in \{1,2,\dots ,N\}:D(Y,1)\le D(X,1)\text{ và }D(Y,2)\le D(X,2)\}|$$

Ngoài ra, doanh nghiệp cũng cam kết với chính quyền địa phương rằng trước khi đặt trung tâm chế tạo thép ở thành phố $X$ nào đó, họ sẽ cải tạo một con đường nối với thành phố $X$. Doanh nghiệp đã khảo sát và đưa ra $P$ phương án. Với phương án thứ $j$ $(1\le j\le P)$, con đường $T_j$ nối giữa thành phố $U_{T_j}$ và $V_{T_j}$ sẽ được chọn để cải tạo giúp cho độ dài mới $W_{T_j}^{\prime }$ bé hơn độ dài ban đầu $W_{T_j}$. Với mỗi phương án, sau khi cải tạo đường, doanh nghiệp cần tính hạng của thành phố $U_{T_j}$ và thành phố $V_{T_j}$. Các phương án là độc lập, nghĩa là các phương án đều chỉ áp dụng lên hiện trạng ban đầu của $M$ con đường.

Yêu cầu: Với phương án thứ $j$ $(1\le j\le P)$, hãy giúp doanh nghiệp tìm ra hạng của thành phố $U_{T_j}$ và thành phố $V_{T_j}$ sau khi cải tạo con đường $T_j$.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $N$, $M$ và $P$ lần lượt là số lượng thành phố, số lượng con đường và số lượng phương án $(2\le N\le {10}^5;1\le M,P\le {10}^5)$.
• Dòng thứ $i$ trong số $M$ dòng tiếp theo chứa ba số nguyên $U_i$, $V_i$ và $W_i$ lần lượt là hai thành phố được nối bởi con đường số $i$ và độ dài của con đường này $(1\le U_i,V_i\le N;1\le W_i\le {10}^9)$.
• Dòng thứ $j$ trong số $P$ dòng tiếp theo chứa hai số nguyên $T_j$ và $W_{T_j}^{\prime }$ lần lượt là chỉ số con đường được lên phương án cải tạo và độ dài sau khi cải tạo $(1\le T_j\le M;1\le W_{T_j}^{\prime }<W_{T_j})$.

Dữ liệu ra

In ra $P$ dòng, trong đó dòng thứ $j$ ghi ra hai số nguyên $R(U_{T_j})$ và $R(V_{T_j})$ tương ứng là hạng của thành phố $U_{T_j}$ và thành phố $V_{T_j}$ nếu phương án thứ $j$ được triển khai.

Ràng buộc

• $2\le N\le {10}^5$; $1\le M,P\le {10}^5$.
• $1\le U_i,V_i\le N$, $U_i\ne V_i$; $1\le W_i\le {10}^9$; giữa hai thành phố có tối đa một con đường; mọi thành phố đều có đường đi tới thành phố khác.
• $1\le T_j\le M$; $1\le W_{T_j}^{\prime }<W_{T_j}$.

Subtasks

• Subtask 1 ($20\%$ số điểm): $M,P\le 1000$.
• Subtask 2 ($20\%$ số điểm): Mỗi thành phố có nhiều nhất $2$ con đường nối với thành phố khác.
• Subtask 3 ($20\%$ số điểm): Mọi con đường đều nối với thành phố số $1$ hoặc thành phố số $2$.
• Subtask 4 ($20\%$ số điểm): $M=N-1$.
• Subtask 5 ($20\%$ số điểm): Không có ràng buộc gì thêm.

Ví dụ