## Another Random Contest 1 P5 - A Strange Country

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

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

All edges are bidirectional.

There will be no self-loops, but there can be multiple edges running through the same pair of nodes.

#### 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.