ZOJ Problem Set - 2697
After recent blackouts in some regions in North America, the government has decided to reorganize the power supply network of the continent.
The power supply network is the set of nodes, such as power plants or transformation stations, connected by transmission lines. All lines are used to transmit electricity from one node to another. For stability reasons the system is organized in such a way that there are no directed cycles.
Since the government is currently short of money due to several small peaceful militaristic operations, it cannot build new power lines for the moment. So after reorganization the same lines will be used, but some lines will have to transmit electricity in the direction opposite to the current one. To make the reorganization gentle enough, the management of the power network is planning to switch the transmission direction for exactly one line each day. Of course, no day there must be a cycle in a network, since this may cause damage to the system. The resulting network is also designed to be acyclic.
Help them to plan the reorganization.
There are mutilple cases in the input file.
The first line of the input file contains n --- the number of nodes in the network, and m --- the number of transmission lines (2 <= n <= 1,000 , 1 <= m <= 10,000 ). The following m lines contain three integer numbers each. The first two give the source and the destination node for the corresponding line in the current node. The third number is 0 if the line must keep its transmission direction in the resulting network, and 1 if the direction must be reversed.
There can be several lines connecting the same pair of nodes, but due to acyclicity condition, they all transmit electricity in the same direction. This is also the reason why no line connects a node to itself.
There is an empty line after each case.
First output k --- the number of days in the plan you suggest. You don't need to minimize this number, but it must not exceed 4m . After that print k integer numbers --- for each day output the number of the line that changes the transmission direction this day. If it is impossible to make the desired reorganization, output -1 instead of k .
There should be an empty line after each case.
4 5 1 2 0 2 3 1 2 4 1 1 4 1 4 3 0 2 2 1 2 1 1 2 1
3 3 2 4 -1
Source: Andrew Stankevich's Contest #9