Task ordering P16249


Statement
 

pdf   zip

html

There are n tasks to be done, but some tasks must be done before others. Given the names of the tasks and the direct dependencies among them, print the lexicographically smallest ordering of the tasks.

Input

Input consists of several cases. Each case begins with n, followed by n names of tasks. Follow the number of direct dependencies m, followed by m pairs of names x y, to indicate that x must be done before y. Assume 1 ≤ n ≤ 104, 0 ≤ m ≤ 10n, that the names are made up of between one and six lowercase letters, that no name is a prefix of another name (in particular, this excludes equal names), that there are no repeated dependencies, and that there are no dependencies of the kind x x.

Output

For every case, print the alphabetically smaller string that can be produced by concatening a valid ordering of the tasks. If there is no valid ordering, tell so.

Public test cases
  • Input

    4  a sample this is
    3
    this is
    is sample
    is a
    
    3  and this too
    0
    
    2  a b
    2
    a b
    b a
    

    Output

    thisisasample
    andthistoo
    NO VALID ORDERING
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Novè Concurs de Programació de la UPC - Semifinal
    Date
    2011-06-29