Words with a, b and c (1) P87741


Statement
 

pdf   zip

thehtml

In this problem we consider words of size n made up only of letters ‘a’, ‘b’ and ‘c’, and without two or more consecutive equal letters. Suppose that some positions of the word have fixed letters. Write a program to print all the words that meet these constraints.

Input

Input consists of several cases. Every case starts with n, followed by the number of fixed positions f, followed by f pairs pi ci, where pi is a position between 0 and n − 1 and ci is ‘a’, ‘b’ or ‘c’. Suppose 1 ≤ n ≤ 15, 0 ≤ fn, and that all pi’s are different.

Output

For every case, print in alphabetical order all words that satisfy the constraints. Print a line with 20 dashes at the end of each case.

Public test cases
  • Input

    2 0
    3 1  2 b
    1 1  0 a
    2 2  0 b  1 b
    4 2  3 a  0 a
    

    Output

    ab
    ac
    ba
    bc
    ca
    cb
    --------------------
    acb
    bab
    bcb
    cab
    --------------------
    a
    --------------------
    --------------------
    abca
    acba
    --------------------
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++