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.
Constraints
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.
Input Specification
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 Specification
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.
Sample Input
3 5 2
1 2 3
1 2 1
2 3 4
2 3 6
1 3 2
Sample Output
2
1
2
-1
1
Sample Explanation
On the first day, roads and
are activated. On the second day, roads
and
are activated. Note that road
is never activated.
Comments