ABC031D

ABC031D.cpp

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define var auto
#define mod 1000000007
#define inf 2147483647
#define nil -1
typedef long long ll;

using namespace std;

inline int input(){
    int a;
    cin >> a;
    return a;
}

template <typename T>
inline void output(T a, int p) {
    if(p){
        cout << fixed << setprecision(p)  << a << "\n";
    }
    else{
        cout << a << "\n";
    }
}

// end of template

int main() {
    cin.tie(0);
    // source code
    int K = input();
    int N = input();
    int num = pow(3, K);
    vector<int> seq(K, 0);
    vector<string> V(N), W(N);
    
    rep(i, N){
        cin >> V[i] >> W[i];
    }
    
    vector<string> str(K);
    
    rep(i, num){
        rep(j, K){
            str[j] = "";
        }
        int impflag = false;
        int tmp = i;
        rep(j, K){
            seq[j] = tmp % 3 + 1;
            tmp = (tmp - seq[j] + 1) / 3;
        }
        
        rep(j, N){
            int ln = 0;
            rep(k, V[j].size()){
                ln += seq[V[j][k] - '1'];
            }
            if (ln != W[j].size()) {
                impflag = true;
            }
        }
        if (impflag) {
            continue;
        }
        rep(j, N){
            int now = 0;
            rep(k, V[j].size()){
                if (str[V[j][k] - '1'] == "" || str[V[j][k] - '1'] == W[j].substr(now, seq[V[j][k] - '1'])) {
                    str[V[j][k] - '1'] = W[j].substr(now, seq[V[j][k] - '1']);
                    now += seq[V[j][k] - '1'];
                }
                else{
                    impflag = true;
                }
                    
            }
            
        }
        if (impflag) {
            continue;
        }
        else{
            rep(j, K){
                output(str[j], 0);
            }
            return 0;
        }
        
    }
    
    return 0;
}