p393.ans1
======================
2
ac
b

=================
p393.ans2
======================
2
cb
ad

=================
p393.ans3
======================
4
ae
b
c
d

=================
p393.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, m;
vector<string> edges;

void read() {
    cin >> n >> m;
    edges.resize(m);
    cin >> edges;
}

void solve() {
    // We want to partition the N letters into subsets (buttons), such that     
    // there are less than two edges between each subset. We will do a brute
    // force approach, where if we iterate through all subsets it would be
    // around BellNumber(N) ~= 27M subsets. This might be a bit tight to
    // pass, because we also have an O(M) or O(N) to check if the subsets
    // violate the constraints. One optimization is to do binary search on the
    // K, which should cut the number of subsets we consider by at least
    // a half. Another optimization is to also recursively generate the
    // subsets. Then instead of going through all StirlingNumber(N, K)
    // subsets, we will only go through the ones that are valid based on the
    // constraints. Furthermore, if we find one valid configuration for a
    // given K, we don't have to continue.

    vector<int> out_edges(n, 0);
    vector<int> in_edges(n, 0);
    for(const auto& e: edges) {
        int u = e[0] - 'a';
        int v = e[1] - 'a';
        out_edges[u] |= (1 << v);
        in_edges[v] |= (1 << u);
    }

    int masks = 1 << n;
    vector<int> any_out(masks);
    vector<int> dang_out(masks);
    vector<int> int_cnt(masks);

    auto precompute = [&]() {
        any_out[0] = dang_out[0] = int_cnt[0] = 0;
        for(int mask = 1; mask < masks; mask++) {
            int u = __builtin_ctz(mask);
            int prev = mask ^ (1 << u);
            any_out[mask] = any_out[prev] | out_edges[u];
            dang_out[mask] = dang_out[prev] | (any_out[prev] & out_edges[u]);
            int_cnt[mask] = int_cnt[prev] +
                            __builtin_popcount(out_edges[u] & prev) +
                            __builtin_popcount(in_edges[u] & prev) +
                            ((out_edges[u] >> u) & 1);
        }
    };

    auto compatible = [&](int g, int h) -> bool {
        if(dang_out[g] & h) {
            return false;
        }
        if(__builtin_popcount(any_out[g] & h) > 1) {
            return false;
        }
        if(dang_out[h] & g) {
            return false;
        }
        if(__builtin_popcount(any_out[h] & g) > 1) {
            return false;
        }
        return true;
    };

    precompute();

    int best_k = n;
    vector<int> best_groups(n);
    for(int i = 0; i < n; i++) {
        best_groups[i] = (1 << i);
    }

    vector<int> groups(n);
    bool found;

    function<void(int, int, int)> dfs = [&](int remaining, int used, int k) {
        if(found) {
            return;
        }
        if(remaining == 0) {
            found = true;
            best_k = used;
            for(int i = 0; i < used; i++) {
                best_groups[i] = groups[i];
            }
            return;
        }
        if(used >= k) {
            return;
        }

        int lo = remaining & (-remaining);
        int rest = remaining ^ lo;

        for(int sub = rest;; sub = (sub - 1) & rest) {
            int group = sub | lo;
            if(int_cnt[group] <= 1) {
                bool good = true;
                for(int i = 0; i < used && good; i++) {
                    if(!compatible(group, groups[i])) {
                        good = false;
                    }
                }
                if(good) {
                    groups[used] = group;
                    dfs(remaining ^ group, used + 1, k);
                    if(found) {
                        return;
                    }
                }
            }
            if(sub == 0) {
                break;
            }
        }
    };

    int left = 1, right = n, mid;
    while(left <= right) {
        mid = (left + right) / 2;
        found = false;
        dfs((1 << n) - 1, 0, mid);
        if(found) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    cout << best_k << '\n';
    for(int i = 0; i < best_k; i++) {
        for(int j = 0; j < n; j++) {
            if(best_groups[i] & (1 << j)) {
                cout << (char)('a' + j);
            }
        }
        cout << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}

=================
p393.in1
======================
3 3
ab
aa
bc

=================
p393.in2
======================
4 2
ab
cd

=================
p393.in3
======================
5 4
aa
bb
cc
dd

=================
statement.txt
======================
393. Bergamot Problem
Time limit per test: 1.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Berland alphabet consists of N letters, which are first N latin letters. Citizens of Berland use simple abbreviation scheme for SMS writing purposes. Each word is abbreviated to the sequence of two symbols — its first and last letters. For example, the word "" is abbreviated to "". Unfortunately, for single-letter words this rule leads to a word lengthening. For example, word "" will be written as "".

Vocabulary used for SMS creation consists of only two-character words. The numerous studies of well-known scientists showed that the vocabulary consists of M distinct words.

Bergamot company is ready to put their new cell phone in production. The new model is planned to have the revolutionary system of a quick text input (somewhat similar to the famous T9). Keyboard of the phone will consist of K buttons. Each button will have one or several letters from placed on it. Each letter can be placed on exactly one button of the phone. In order to enter a word, a user should press two buttons on the phone one after another: button with the first letter of the word, and then button with the last letter of the word. Placement of letters on the keyboard is called  for a given vocabulary, if there are no words from vocabulary that can be entered using the same two-buttons sequence.

For example, if the vocabulary consists of three words "", "" and "", two buttons are enough for creating the keyboard. The first button will have "" and "", the second button — "". The placement like "" and "" on the first button, "" on the second button will not work, because words "" and "" can be entered using the same sequence of buttons.

Bergamot engineers have got a problem finding optimal placement of Berland alphabet letters on the keyboard of the phone. The  placement is any correct placement with the minimal possible number of buttons used for the given Berland alphabet.

Input
The first line of the input contains two integer numbers N, M (1 ≤ N ≤ 13; 0 ≤ M ≤ 50). The following M lines contain words from the vocabulary — one word per line. Each word consists of exactly two lowercase Latin letters. Only first N letters from Latin alphabet can be used. All words in the vocabulary are different.

Output
The first line of the output file should contain the minimal possible number of the keyboard buttons K for the optimal letters placement. The placement itself should be printed to the following K lines. The i+1th line of the output file should contain letters placed on the ith button. The order of letters within each line, and the order of lines describing the placement don't matter. If there are several solutions, you may output any of them.

Example(s)
sample input
sample output
3 3
ab
aa
bc
2
ac
b

sample input
sample output
4 2
ab
cd
2
cb
ad

sample input
sample output
5 4
aa
bb
cc
dd
4
ae
b
c
d

=================
