Finally
it’s the big day. The sultan is getting married. Kings, Queens and Diplomats
around the world are coming to attend the Sultan’s weddings. But alas!!! Just
before the grand day the royal treasury was raided. And the Sultan is now very
upset about the security of his guests. As the Sultan’s minister of homeland
security your job is to ensure that the whole kingdom is secured and the grand
day goes on without any drift. The sultan wants that:
1. Every road in the kingdom is
secured by a royal guard.
2. The royal guards are highly
trained. When they are standing on a road intersection they can keep an eye on
every road meeting at that intersection. And you have to place the guards on
the intersection.
3. But guards are human too!! They
get bored while standing on the intersections. When they see another fellow
guard on the other end of a road leaving his intersection he starts to chat
with him and sometimes forget what he was supposed to do!!! The Sultan wants
you to place them in such way that this incident never occurs.
4. You have to ensure that
conditions (1, 2, and 3) are met, and to do this you may even ask the civil
works department to demolish a proper subset of the kingdom roads. The people
in the civil works department are very lazy. They are so lazy that they do not
want to have a list of roads and go demolish them. They just ask for a road
length K and demolish all the roads with length greater or equal to K.
Now
you have to secure the kingdom by conditions [1, 2, 3 and 4] and also maximize K
if any road is needed to be demolished.
The
first line of input will contain an integer T
For
each test case you have to print a single integer in a separate line, the
maximum K if any road is required to be demolished to secure the
kingdom by conditions [1, 2, 3 and 4]. Print 0 if no road is required to
be demolished. Print -1 if it is impossible to secure the kingdom by
conditions [1, 2, 3 and 4].
Sample Input |
Output for Sample Input |
1 4 5 1 2 1 3 1 7 2 3 3 2 4 11 3 4 5 |
7 |
|
|
Problemsetter:
|
Shihabur Rahman Chowdhury |
Special Thanks:
|
Md. Mahbubul
Hasan
|