Untitled

def parse_and_chain(input_string):
    """
    Parses the input string, extracts P and Q, and builds a word chain 
    starting from 'starter', resolving conflicts alphabetically by the next word.
    """
    parts = input_string.split(';')

    try:
        # Extract P and Q
        pq_numbers = parts[0].split()
        P = int(pq_numbers[0])
        Q = int(pq_numbers[1])
        
        # Create list of word pairs
        word_pairs = [item.strip().split() for item in parts[1:]]
        
    except (IndexError, ValueError):
        return "Error: Invalid format for P and Q. Ensure the input starts with 'P Q ;'."

    # --- Chain Building Logic ---
    
    starter_word = 'starter'
    chain = [starter_word]
    current_word = starter_word

    used_indices = set()
    total_pairs = len(word_pairs)

    while len(used_indices) < total_pairs:
        
        # 1. Find all possible, unused links starting from the current word
        possible_next_links = []
        for i, pair in enumerate(word_pairs):
            if i not in used_indices and pair[0] == current_word:
                possible_next_links.append({'index': i, 'next_word': pair[1]})

        if not possible_next_links:
            break
        
        # 2. Apply the alphabetical tie-breaker (sorts by 'next_word')
        # This handles the 'starter' choice and all subsequent choices.
        possible_next_links.sort(key=lambda x: x['next_word'])
        
        # Select the best choice
        best_link = possible_next_links[0]
        
        # 3. Update the chain and state
        next_word = best_link['next_word']
        used_index = best_link['index']
        
        chain.append(next_word)
        current_word = next_word
        used_indices.add(used_index)
        
    return chain

# --- Main Execution ---

input_string = input()

final_chain = parse_and_chain(input_string)

# Print the final result
print(final_chain)