Problem E
Matchfixning
Languages
en
sv
Lola och hennes $N-1$ klasskamrater spelar alltid pingis på rasterna. Nu vill Lola utnämna klassens pingismästare och då det bara finns ett pingisbord går det till på följande sätt: Det spelas $N-1$ matcher och alla står i en kö och väntar på sin tur att spela. Den som vinner matchen får stå kvar vid bordet och möta den som står näst på tur i kön. Personen som vinner den sista matchen koras till klassens pingismästare.
Lola tycker väldigt mycket om både pingis och statistik och har därför noterat resultaten i alla pingismatcher som någonsin har spelats mellan hennes klasskamrater. Därför vet hon alltid vem som vinner när två personer möts. Det är dessutom garanterat att någon vinner, en match kan aldrig sluta oavgjort. Nu vill hon utnyttja detta för att skapa en köordning sådan att hon själv blir pingismästare oavsett vad. Givet vilka personer som vinner över varann, kan du hjälpa Lola skapa en sådan köordning?
Indata
Första raden innehåller ett heltal $N$ ($2
\leq N \leq 1000$), hur många personer som går i Lolas
klass.
Därefter följer $N$ beskrivningar av personerna. Varje beskrivning består av två rader. Den första raden innehåller namnet på personen och hur många personer hen vinner över. Den andra raden innehåller namnen på alla personer hen vinner över.
Alla namn är strängar som är max $20$ tecken långa och som enbart består av små bokstäver i det engelska alfabetet. Det är garanterat att inga två personer heter samma sak och att namnet ”lola” alltid finns med i indatan.
Utdata
Skriv ut en köordning sådan att Lola blir pingismästare. Om det finns flera giltiga ordningar kan du skriva ut vilken som. Om det inte finns någon sådan ordning ska du skriva ut $-1$.
Poängsättning
Din lösning kommer att testas på flera olika testgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poäng |
Gränser |
|
$1$ |
$14$ |
$N = 10$ |
|
$2$ |
$17$ |
$N = 20$ |
|
$3$ |
$20$ |
$N = 100$ |
|
$4$ |
$49$ |
Inga ytterligare begränsningar. |
Förklaring
I första exempelfallet kan man först låta Beata möta Anna. Då kommer Beata vinna. Sedan kan Beata möta Lola. Då kommer Lola vinna. Därför funkar köordningen Anna - Beata - Lola.
I andra exempelfallet kommer Beata vinna oavsett vem hon möter. Därför går det inte att skapa en köordning.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 anna 1 lola beata 1 anna lola 1 beata |
anna beata lola |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 anna 2 beata lola beata 0 lola 1 beata |
Impossible |
| Sample Input 3 | Sample Output 3 |
|---|---|
5 lola 2 david angela david 2 bobo angela casper 2 lola david angela 2 bobo casper bobo 2 casper lola |
david bobo casper angela lola |
