Otun dəyişdirilməsi#10530
Fermer Con müxtəlif inək cinslərinin müxtəlif ot növlərinə üstünlük verdiyini aşkar etmişdir. Bununla belə, otları elə diqqətlə əkmək lazımdır ki, inəklərə zərər dəyməsin.
Conun fermasında tarla var və cüt tarla ikitərəfli yollarla birləşdirilib. Bu yollarla istənilən tarladan istənilən başqa tarlaya çatmaq mümkündür. Hər bir yolun uzunluğu -dən 10^6-a qədər (daxil olmaqla) tam ədəddir. İstənilən cüt tarla arasında birbaşa yol ən çox bir dənə ola bilər.
Əvvəlcə Fermer Con hər bir tarlada ot növündən birini əkir. Zaman keçdikcə o, bəzi tarlalarda bitən ot növünü dəyişə bilər. Bu əməliyyat yeniləmə adlanır.
Hər bir yeniləmədən sonra Fermer Con üzərində müxtəlif ot növləri bitən iki tarla arasındakı ən qısa yolun uzunluğunu bilmək istəyir. Başqa sözlə, müxtəlif ot növlərinə malik olan bütün tarla cütləri arasından o, onlar arasındakı mümkün olan ən kiçik məsafəni tapmaq istəyir. Zəmanət verilir ki, istənilən anda müxtəlif ot növlərinə malik olan ən azı bir cüt tarla mövcuddur.
Birinci sətirdə dörd tam ədəd verilir: n~(1 \le n \le 2 \cdot 10^5), m~(1 \le m \le 2 \cdot 10^5), k~(1 \le k \le n) və q~(1 \le q \le 2 \cdot 10^5), burada — yeniləmə əməliyyatlarının sayıdır.
Sonrakı sətir yolları təsvir edir. Hər sətir üç tam ədəddən ibarətdir və , bu isə o deməkdir ki, və tarlaları uzunluğu olan ikitərəfli yolla birləşdirilib, burada 1 \le a, b \le n.
Sonrakı sətirdə hər bir tarlada olan ilkin ot növünü təsvir edən tam ədəd verilir. Hər bir qiymət -dən -ya qədər diapazondadır.
Sonrakı sətir yeniləmə əməliyyatlarını təsvir edir. Hər sətir iki tam ədəddən ibarətdir və , bu isə o deməkdir ki, tarlasındakı ot növü -yə dəyişdirilir.
Hər bir yeniləmə əməliyyatı üçün müvafiq yeniləmə yerinə yetirildikdən sonra müxtəlif ot növlərinə malik olan iki tarla arasındakı ən qısa yolun uzunluğunu çap edin.
Nümunə 1