NC25362. Battlefields
描述
Chairman Mao said: "It is a very important military principle to save yourself and destroy the enemy." Qleonardo keeps this principle in mind and practices it in every training exercise.
However, the battlefield of the future is changing rapidly. This means that our military maps are not fixed. Our map can be thought of as an undirected connected graph with n nodes and n edges.
In a military exercise, we assume that there is an enemy on each road, and each enemy has a colored flag on it. If you defeat this enemy, then you can take this flag. However, no matter how powerful you are, your enemies find that you have taken the same color flag as him, and he can defeat you more than the flag of the corresponding color. After all, the power of revenge is very powerful. In addition, every time you go through a road, you can't take this road again for security reasons.
Now the commander has given Qleonardo m missions, each of which requires him to travel from node x to node y and get as many flags as possible along the way. At this point, Qleonardo remembered Chairman Mao's words ……
You can help Qleonardo calculate that for each mission, he can get up to several flags. You can think of Qleonardo strong enough.
输入描述
The first line consists of three numbers n,m(2<=n,m<=200,000), representing the number of nodes and the number ofmissions assigned by commander to Qleonardo and the change of map.
Next n lines, each line has three numbers x,y(1<=x,y<=200,000) and col (1<=col<=1,000) , which respectively representthe two endpoints of an edge and the color of the flag taken by the enemy onthis side.
Next m lines, the first number op of eachline represents the operation instruction.
When op is 0, followed by two numbers u andv, indicating that the color of the flag taken by the enemy on the x-th edge ischanged to y.
When op is 1, followed by two numbers u andv for the commander's assignment to Qleonardo.
输出描述
For each mission assigned by the commander,output the maximum number of flag colors that Leonardo can get in a line.
If the missions assigned by the commandercannot be completed, then output -1.
示例1
输入:
5 3 1 5 1 2 1 2 3 2 3 4 3 4 5 4 5 1 4 5 0 4 2 1 4 5
输出:
4 2