Another Random Contest 1 P5 - A Strange Country

View as PDF

Submit solution

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

Problem type

In a strange country, there are N cities numbered 1 to N, and M roads numbered 1 to M. 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 K days it was activated or output that the road is never activated in the K following days.


For all subtasks:

1 \le N \le 5 \times 10^3

1 \le K \le 10^4

0 \le M \le 3 \times 10^5

1 \le u_i, v_i \le N

1 \le w_i \le 10 ^ 9

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%]

0 \le M \le 1\,000

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line contains three integers N, M, and K.

The following M lines contain three integers u_i, v_i, w_i, meaning there is a road connecting u_i and v_i with a cost of w_i to activate.

Output Specification

Output M lines, the ith line contains an integer representing which day the ith road in the order of input is activated, or -1 if the road is never activated in the K days.

Sample Input

3 5 2
1 2 3
1 2 1
2 3 4
2 3 6
1 3 2

Sample Output


Sample Explanation

On the first day, roads 2 and 5 are activated. On the second day, roads 1 and 3 are activated. Note that road 4 is never activated.


There are no comments at the moment.