GCPC11C - Indiana Jones and the lost Soccer Cup

no tags 

In 1930 the first FIFA World Cup was held in Uruguay, and Uruguay won the Cup in a dramatic final against Argentina. All of this seems like ages past, and now myth and legend rank around that historic first world cup. Some even claim that the original trophy cup that was awarded to Uruguay for their victory has mythical powers and would grant any side the strength to win the World Cup.

Now that original cup has been lost in time, and even though its mythical powers are probably just stories, it is still an important artifact which belongs in a museum. Clearly an expert is needed to recover it.

Famous archaeologist and adventurer Indiana Jones has taken this dangerous task onto himself and traveled to Uruguay to find the cup. His search has led him to an ancient underground cave system where the cup is rumoured to have been hidden. Many traps lure within these caves, and only his instinct and his faithful whip have saved Indy from certain death. Now he has reached a mysterious enormous gate and he can only speculate that the cup must be hidden behind that gate. Unfortunately it is shut close.

The gate is riddled with switches and levers, and all of them are denoted with letters and numbers. As you may have guessed, the gate will only open if the switches and levers are pulled in the correct order, but beware! - For if anyone is unlucky enough to get the order wrong, doom awaits him.

Luckily, during his exploration of the caves Indy has found several encrypted hints which provide clues about the correct sequence. Here's one: "The faithful knows that X comes before O" And another: "Under no circumstances should you touch a unless b has been moved!" Clearly these clues give hints about the correct order, but there are a lot of switches and levers, and there are lots of clues. Indy needs help!

Given all of the hints Indy has collected, can you help him determine the correct order of the levers and switches so that he can successfully complete his adventure? But beware - Indy could have missed some hints; or perhaps he misinterpreted some of them. The former case will likely leave more than one possible sequence while the latter will lead to no possible sequence at all. You must detect these cases and warn Indy.


The first line of input contains the number of test cases C (C ≤ 30). For each test case there is one line with the number n (1 ≤ n ≤ 104) of switches/levers on the gate and the number h (0 ≤ h ≤ 105) of hints that Indy has discovered. Then follow h lines, one for each clue, with the numbers a and b (1 ≤ a,b ≤ n, a ≠ b), meaning that lever a must be pulled before lever b.


For each test case output one line with the correct sequence of the numbers 1 to n. Separate the numbers with a whitespace. If there is no possible sequence, print recheck hints instead. Otherwise if there are multiple possible sequences, print missing hints instead.


3 2
1 2
3 1
3 1
1 2
3 2
1 2
2 1

3 1 2
missing hints
recheck hints

hide comments
omar: 2017-07-03 03:16:52

please add this test:
4 4
3 2
3 1
2 1
2 4
my wrong greedy solution passed because no such test

avrupa: 2016-06-26 06:25:27

Last edit: 2016-06-26 08:36:42
tushar aggarwal: 2014-08-22 10:22:54

ans shud be missing hints

Arshu jain: 2014-04-03 14:05:42

what is the answer for test case
6 6
2 1
3 2
4 3
5 1
6 5
4 7

missing hints or 4 3 2 6 5 1

Adrian Kuegel: 2011-08-26 08:39:35

The test data was weak, I added new test cases and made a rejudge.

Adrian Kuegel: 2011-08-26 08:36:57

@anksanu: Your algorithm is the main reason why your program is so slow. It is O(n^2) in the worst case.

anksanu: 2011-08-26 08:36:57

stl takes a shear lot of time .......

Adrian Kuegel: 2011-08-26 08:36:57

That is not true, I have asserts in my code which would lead to runtime error if there are any values > n.

Santiago Palacio: 2011-08-26 08:36:57

There can be hints whose numbers are greater than "n"? example:
3 3
5 2
3 2
2 1

Problem Solver: 2011-08-26 08:36:57

check you output for
1 0
btw i hate programming in notepad :(

Last edit: 2011-07-11 14:01:33

Added by:Adrian Kuegel
Time limit:1.666s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:German Collegiate Programming Contest 2011 (Author: Holger Frydrych)