FJ's farm consists of NN fields (1≤N≤200,0001≤N≤200,000), where MM pairs of fields are connected by bi-directional pathways (1≤M≤200,0001≤M≤200,000). Using these pathways, it is possible to walk from any field to any other field. Each pathway has an integer length in the range 1…1,000,0001…1,000,000. Any pair of fields will be li
In each field, FJ initially plants one of KK types of grass (1≤K≤N1≤K≤N). Over time, however, he might decide to switch the grass in some field to a different type. He calls this an "update" operation. He might perform several updates over the course of time, which are all cumulative in nature.
After each update, FJ would like to know the length of the shortest path between two fields having different grass types. That is, among all pairs of fields having different grass types, he wants to know which two are closest. Ideally, this number is large, so he can prevent grass of one type from mixing with grass of another type. It is guaranteed that the farm will always have at least two fields with different grass types.
In 30 percent of the input cases, each field will be directly connected to at most 10 pathways.
3 2 3 4
1 2 3
2 3 1
1 1 2
3 3
2 3
1 2
2 21
3
3
1