No tags yet

No tag edit access

Time limit per test: 1 second(s)

Memory limit: 262144 kilobytes

Memory limit: 262144 kilobytes

input: standard

output: standard

output: standard

Once upon a time, long, long ago there lived a King and a Queen who ruled over a distant kingdom called Berland.

Their kingdom contained

One day the King and the Queen decided that they want to break up the relationship. Yes, it's not common when it comes to a royal marriage, but it's something they decided to do and we have to respect their decision. Of course, now they want to divide the kingdom and start living separately from each other. Each of them wants to take a part of the existing kingdom. Moreover, they want their own parts to be very special, so their requirements are quite complicated.

So, the King wants to pick a nonempty subset of cities from the existing kingdom. He will be satisfied only if all following conditions are met:

- his subset of cities is connected (i.e. for every pair of his cities
*A*and*B*, there is always a path from*A*to*B*that passes only through the King's cities), - he does not share any cities with the Queen,
- none of his cities are directly connected by a road to any of the Queen's cities,
- if you consider distances between all pairs of his cities, the length of the longest path must be equal to
*D*_{1}, - if you consider all pairs of his cities which are located at distance
*D*_{1}from each other and then calculate the number of different cities within all these pairs, this number must not exceed*C*_{1}(formally, if his subset contains the only city then the number of such pairs equals 0).

The Queen wants to pick a nonempty subset of cities as well. Her requirements are essentially the same as the King's ones, with the exception of the numbers she has in mind —

Now, what about the remaining cities, the ones that will not belong to either the King or the Queen after the kingdom is divided? The answer is simple — they have to be destroyed along with all roads coming into them, and all people should be evacuated from these cities. Destroying the

Can you help the King and the Queen with the separation? You task is to figure out whether it's possible to perform separation of the kingdom according to the rules described above. If the separation is possible, you have to find a way with the minimum possible cost of cities that will be destroyed.

-1" (without the quotes) in a single output line.

Otherwise, output the total cost of destroyed cities in the first line, and print the numbers of destroyed cities in the increasing order in the second line. If there are multiple solutions, you may print any of them.

sample input | sample output |

10 4 2 0 1 5 2 5 2 5 5 5 5 5 2 1 4 6 1 1 2 7 1 3 7 10 7 9 10 7 8 8 5 | 6 2 4 10 |

sample input | sample output |

4 1 2 1 2 9 9 9 9 1 2 2 3 3 4 | -1 |

- In the first place, city 10 is destroyed and the kingdom falls apart into two parts. The smallest part contains an isolated city 9, and it already satisfies the Queen's requirements.
- The second remaining part is a little bit too large for the King. The maximum distance between pairs of cities (2,5), (4,5), (6,5) is 4, exactly as the King wants. But the number of these cities [2, 4, 5, 6] is 4, while the King's desire is to have not more than 2. So, it's additionally required to destroy cities 2 and 4.
- Overall, destroying cities [2, 4, 10] costs 6 burles. It's an optimal solution from the cost perspective.

In the second test case there is no solution. Obviously, at least one city should be deleted from the kingdom, while

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/16/2019 01:33:17 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|