In a strange country, there are cities numbered to , and roads numbered to . The government would like to connect as many cities together as possible for the minimum cost. Every day, they will activate the current minimum spanning tree/forest.
Two cities are considered connected if they can be reached directly or indirectly from one another. A bidirectional road connects two cities and has a cost to activate.
It is worth noting that all costs are distinct, which means there is always only one way to form the minimum spanning tree/forest. However, after every day, the people of the country tend to destroy roads, and a road that was activated for the day will not be usable for the rest of eternity. Thus, the government will activate a new set of roads the day after according to the same rule. The government wants to know for each road which day in the following days it was activated or output that the road is never activated in the following days.
For all subtasks:
All edges are bidirectional.
There will be no self-loops, but there can be multiple edges running through the same pair of nodes.
Subtask 1 [30%]
Subtask 2 [70%]
No additional constraints.
The first line contains three integers , , and .
The following lines contain three integers , , , meaning there is a road connecting and with a cost of to activate.
Output lines, the th line contains an integer representing which day the th road in the order of input is activated, or if the road is never activated in the days.
3 5 2 1 2 3 1 2 1 2 3 4 2 3 6 1 3 2
2 1 2 -1 1
On the first day, roads and are activated. On the second day, roads and are activated. Note that road is never activated.