Gần đây, Farmer John đang thử nghiệm trồng các loại cỏ khác nhau trên trang trại vì nhận ra rằng những loại bò khác nhau thích những loại cỏ khác nhau. Tuy nhiên, ông phải cẩn thận để đảm bảo các loại cỏ khác nhau được trồng đủ xa nhau, tránh cho chúng bị trộn lẫn đến mức không thể tách rời.

Trang trại của FJ gồm \(N\) cánh đồng (\(1 \leq N \leq 200\,000\)), trong đó \(M\) cặp cánh đồng được nối với nhau bằng các đường đi hai chiều (\(1 \leq M \leq 200\,000\)). Có thể đi từ một cánh đồng bất kỳ đến mọi cánh đồng khác bằng các đường đi này. Mỗi đường đi có độ dài nguyên trong khoảng \(1 \ldots 1\,000\,000\). Mỗi cặp cánh đồng được nối trực tiếp bởi nhiều nhất một đường đi.

Ban đầu, FJ trồng một trong \(K\) loại cỏ trên mỗi cánh đồng (\(1 \leq K \leq N\)). Tuy nhiên, theo thời gian, ông có thể quyết định đổi loại cỏ trên một cánh đồng nào đó sang loại khác. Ông gọi đây là một thao tác "cập nhật". Ông có thể thực hiện nhiều lần cập nhật theo thời gian, và tất cả các cập nhật đều có hiệu lực tích lũy.

Sau mỗi lần cập nhật, FJ muốn biết độ dài đường đi ngắn nhất giữa hai cánh đồng trồng hai loại cỏ khác nhau. Nói cách khác, trong tất cả các cặp cánh đồng có loại cỏ khác nhau, ông muốn biết hai cánh đồng gần nhau nhất. Lý tưởng nhất là giá trị này lớn, nhờ đó ông có thể ngăn cỏ thuộc loại này trộn lẫn với cỏ thuộc loại khác. Dữ liệu được đảm bảo rằng trang trại luôn có ít nhất hai cánh đồng trồng hai loại cỏ khác nhau.

Phân nhóm

• Trong \(30\%\) số bộ dữ liệu, mỗi cánh đồng được nối trực tiếp với nhiều nhất \(10\) đường đi.

Dữ liệu vào

Dòng đầu tiên chứa bốn số nguyên \(N\), \(M\), \(K\) và \(Q\), trong đó \(Q\) là số lần cập nhật (\(1 \leq Q \leq 200\,000\)).

\(M\) dòng tiếp theo mô tả các đường đi; mỗi dòng chứa ba số nguyên \(A\), \(B\) và \(L\), cho biết có một đường đi độ dài \(L\) từ cánh đồng \(A\) đến cánh đồng \(B\) (cả \(A\) và \(B\) đều nằm trong khoảng \(1 \ldots N\)).

Dòng tiếp theo chứa loại cỏ ban đầu được trồng trên mỗi cánh đồng (\(N\) số nguyên trong khoảng \(1 \ldots K\)).

Cuối cùng, \(Q\) dòng cuối, mỗi dòng mô tả một lần cập nhật bằng hai số nguyên \(A\) và \(B\), nghĩa là cỏ trên cánh đồng \(A\) được đổi thành loại \(B\).

Dữ liệu ra

Với mỗi lần cập nhật, sau khi áp dụng cập nhật đó, hãy in độ dài đường đi ngắn nhất giữa hai cánh đồng trồng hai loại cỏ khác nhau.

Ví dụ

3 2 3 4
1 2 3
2 3 1
1 1 2
3 3
2 3
1 2
2 2

1
3
3
1

Nguồn

USACO 2017 US Open Contest, Platinum — Switch Grass. Tác giả đề: Lewin Gan.

https://usaco.org/index.php?page=viewproblem2&cpid=745