import java.io.*;
import java.util.*;
import java.awt.geom.*;

/**
 * Solution to Politics
 * 
 * @author vanb
 */
public class politics_vanb
{
    public Scanner sc;
    public PrintStream ps;
    
    /** This HashMap will map each candidate to a unique integer, in order */
    public HashMap<String,Integer> candidates = new HashMap<String,Integer>();
    
    /** This count will help us assign a unique integer to each candidate, in order */
    public int count = 0;
    
    /**
     * Add a Candidate.
     * If it's not there yet, give it a number and advance the count.
     * If it's already there, do nothing.
     * 
     * @param candidate A candidate to add
     */
    public void addCandidate( String candidate )
    {
        if( !candidates.containsKey( candidate ) ) candidates.put( candidate, count++ );
    }
    
    /**
     * This class will store a Candidate/Supporter pair, and has a comparator that will help
     * to sort them by index.
     * 
     * @author vanb
     */
    public class Supporter implements Comparable<Supporter>
    {
        /** Index, value */
        public String candidate, supporter;
        public int order;
        
        /**
         * Create an Indexed Value
         * @param candidate The index
         * @param supporter The value
         */
        public Supporter( String candidate, String supporter, int order )
        {
            this.candidate = candidate;
            this.supporter = supporter;
        }
        
        /**
         * Compare this Supporter to another, first by candidate, then by order.
         * 
         * @param s Another supporter to compare with this one
         * @return -1, 0 or 1, as is usual for compareTo()
         */
        public int compareTo( Supporter s )
        {
            // First, compare by candidate, using the assigned number
            int diff = candidates.get( candidate ).compareTo( candidates.get( s.candidate ) );
            
            // If they have the same candidate, then just compare them by order.
            if( diff==0 ) diff = order - s.order;
            return diff;
        }
    }
      
    /**
     * Driver.
     * @throws Exception
     */
    public void doit() throws Exception
    {
        sc = new Scanner( System.in ); //new File( "politics.in" ) );
        ps = System.out; //new PrintStream( new FileOutputStream( "politics.vanb" ) );

        for(;;)
        {
            int n = sc.nextInt();
            int m = sc.nextInt();
            if( n==0 ) break;
            
            // Read in the candidates
            candidates.clear();
            count = 0;
            for( int i=0; i<n; i++ )
            {
                addCandidate( sc.next() );
            }
            
            // Read in the supporters
            Supporter supporters[] = new Supporter[m];
            for( int i=0; i<m; i++ )
            {
                String supporter = sc.next();
                String candidate = sc.next();
                supporters[i] = new Supporter( candidate, supporter, i );
                
                // Gotta add this candidate if it's not already there
                addCandidate( candidate );
            }
            
            // Sort'em
            Arrays.sort( supporters );
            
            // Print'em
            for( Supporter s : supporters )
            {
                ps.println( s.supporter );
            }
            
        }
    }
    
    /**
     * @param args
     */
    public static void main( String[] args ) throws Exception
    {
        new politics_vanb().doit();
    }   
}