Cambio dell'erba#10530
Il fattore John ha scoperto che razze diverse di mucche preferiscono tipi diversi di erba. Tuttavia, l'erba deve essere piantata con attenzione per non danneggiare le mucche.
La fattoria di John è composta da campi, e coppie di campi sono collegate da strade bidirezionali. Utilizzando queste strade è possibile raggiungere qualsiasi campo da qualsiasi altro. La lunghezza di ogni strada è un numero intero compreso tra e 10^6 inclusi. Tra qualsiasi coppia di campi esiste al massimo una strada diretta.
Inizialmente, il Fattore John pianta su ogni campo uno tra tipi di erba. Con il tempo, può cambiare il tipo di erba che cresce su alcuni campi. Tale operazione viene chiamata aggiornamento.
Dopo ogni aggiornamento, il Fattore John vuole conoscere la lunghezza del cammino più corto tra due campi su cui crescono tipi diversi di erba. In altre parole, tra tutte le coppie di campi con tipi diversi di erba, vuole trovare la minima distanza possibile tra di essi. È garantito che in ogni momento esista almeno una coppia di campi con tipi diversi di erba.
Nella prima riga sono contenuti quattro numeri interi: n~(1 \le n \le 2 \cdot 10^5), m~(1 \le m \le 2 \cdot 10^5), k~(1 \le k \le n) e q~(1 \le q \le 2 \cdot 10^5), dove è il numero di operazioni di aggiornamento.
Le successive righe descrivono le strade. Ogni riga contiene tre numeri interi e , che indicano che i campi e sono collegati da una strada bidirezionale di lunghezza , dove 1 \le a, b \le n.
Nella riga successiva sono contenuti numeri interi che descrivono il tipo di erba iniziale su ciascun campo. Ogni valore è compreso tra e .
Le successive righe descrivono le operazioni di aggiornamento. Ogni riga contiene due numeri interi e , che indicano che il tipo di erba sul campo viene cambiato in .
Per ogni operazione di aggiornamento, stampate la lunghezza del cammino più corto tra due campi con tipi diversi di erba dopo l'esecuzione del rispettivo aggiornamento.
Esempio 1