<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

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

<|response|>
## 1) Abridged problem statement (concise)

You have an alphabet of size **N ≤ 13** (letters `a..`). There are **M ≤ 50** distinct **2-letter words** (ordered pairs) in a vocabulary.

You must partition the N letters into **K buttons** (each letter on exactly one button). A word `xy` is typed by pressing the button containing `x`, then the button containing `y`.

A placement is **correct** if **no two different words** are typed by the **same ordered pair of buttons**.  
Find the **minimum K** and output any valid partition.

---

## 2) Key observations

1. **Graph model**: Treat letters as vertices `0..N-1`. Each word `xy` is a **directed edge** `x → y`.

2. **Buttons = partition into groups**: If letters are partitioned into groups (buttons) `G1..GK`, then typing a word corresponds to an ordered pair of groups `(Gi, Gj)`.

3. **Correctness constraint**:
   For every ordered pair of groups `(A, B)`, there must be **at most one** vocabulary edge `u → v` with `u ∈ A` and `v ∈ B`.  
   This includes the case `A = B` (edges inside one button).

4. **N is small ⇒ bitmasks**: Since `N ≤ 13`, any subset of letters fits into an integer bitmask (0..2^N−1). We can precompute properties for all subsets.

5. **Monotonicity in K**: If a partition is possible with K buttons, it’s also possible with K+1 (split any group).  
   ⇒ We can **binary search** the minimum K and test feasibility.

6. **Avoid huge partition enumeration**: The number of set partitions is large (Bell numbers). Instead, do a **DFS** that:
   - always puts the **lowest remaining letter** into the next group (removes symmetry),
   - enumerates possible groups containing it,
   - prunes by fast compatibility checks.

---

## 3) Full solution approach

### Step A — Build adjacency bitmasks
Index letters `0..N-1`.

- `out[u]`: bitmask of all `v` such that edge `u → v` exists
- `in[v]`: bitmask of all `u` such that edge `u → v` exists

### Step B — Precompute subset information for all `mask`
For each subset `mask`:

1. `any_out[mask]` = union of all outgoing targets from vertices in `mask`  
   `any_out[mask] = OR(out[u])` for `u ∈ mask`

2. `dang_out[mask]` = set of vertices `v` that receive edges from **at least two different** vertices in `mask`  
   This helps detect collisions where two different edges would map to the same button-pair.

3. `int_cnt[mask]` = number of directed edges fully inside `mask`  
   Internal validity requires `int_cnt[mask] ≤ 1` because `(Gi,Gi)` must also have ≤ 1 edge.

All these can be computed by subset DP:
take `u = least significant set bit of mask`, `prev = mask without u`, and update.

### Step C — O(1) compatibility test between two groups
For disjoint groups `g` and `h`, need:
- edges from `g` to `h`: **≤ 1**
- edges from `h` to `g`: **≤ 1**

Using precomputed arrays:

`g → h` is invalid if:
- `dang_out[g]` intersects `h` (some vertex in `h` is hit by ≥2 sources from `g`)
- OR `popcount(any_out[g] & h) > 1` (g hits ≥2 distinct vertices in h)

Check both directions.

### Step D — Feasibility check for a fixed K (DFS)
Goal: partition all letters into **≤ K** groups.

DFS state:
- `remaining` bitmask of unassigned letters
- `used` number of groups already chosen
- list `groups[]` of chosen group masks

Recurrence:
1. If `remaining == 0` ⇒ success.
2. If `used == K` but still remaining ⇒ fail.
3. Let `lo` be the lowest set bit of `remaining`. Force `lo` into the next group.
4. Enumerate all subsets `sub` of `rest = remaining \ {lo}` and set `group = sub ∪ {lo}`.
5. Accept `group` only if:
   - `int_cnt[group] ≤ 1`
   - compatible with all previously chosen groups
6. Recurse on `remaining \ group`.

This generates each partition only once (no permutation duplicates).

### Step E — Binary search minimal K
Binary search `K ∈ [1..N]`:
- run feasibility DFS for mid
- if feasible, try smaller; else try larger
Store the found groups for the best K.

### Complexity
- Precompute over all subsets: `O(N * 2^N)` (≤ ~106k ops)
- DFS is pruned heavily; `N=13` is small enough.
- Works comfortably within limits.

---

## 4) C++ implementation

```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;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

def solve() -> None:
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    m = int(next(it))
    words = [next(it) for _ in range(m)]

    # Directed graph as bitmasks
    out = [0] * n
    inn = [0] * n
    for w in words:
        u = ord(w[0]) - 97
        v = ord(w[1]) - 97
        out[u] |= 1 << v
        inn[v] |= 1 << u

    ALL = 1 << n
    any_out = [0] * ALL     # union of outgoing neighbors from subset
    dang_out = [0] * ALL    # vertices reached by >=2 sources from subset
    int_cnt = [0] * ALL     # count of edges fully inside subset

    # Subset DP precomputation
    for mask in range(1, ALL):
        lsb = mask & -mask
        u = lsb.bit_length() - 1
        prev = mask ^ lsb

        any_out[mask] = any_out[prev] | out[u]
        dang_out[mask] = dang_out[prev] | (any_out[prev] & out[u])

        add1 = (out[u] & prev).bit_count()   # edges u -> v, v in prev
        add2 = (inn[u] & prev).bit_count()   # edges v -> u, v in prev
        loop = (out[u] >> u) & 1             # u -> u
        int_cnt[mask] = int_cnt[prev] + add1 + add2 + loop

    def compatible(g: int, h: int) -> bool:
        # g -> h at most one edge
        if dang_out[g] & h:
            return False
        if (any_out[g] & h).bit_count() > 1:
            return False
        # h -> g at most one edge
        if dang_out[h] & g:
            return False
        if (any_out[h] & g).bit_count() > 1:
            return False
        return True

    best_k = n
    best_groups = [(1 << i) for i in range(n)]
    groups = [0] * n

    sys.setrecursionlimit(1_000_000)

    def feasible(k: int) -> bool:
        nonlocal best_k, best_groups
        found = False

        def dfs(remaining: int, used: int) -> None:
            nonlocal found, best_k, best_groups
            if found:
                return
            if remaining == 0:
                found = True
                best_k = used
                best_groups[:used] = groups[:used]
                return
            if used >= k:
                return

            lo = remaining & -remaining
            rest = remaining ^ lo

            sub = rest
            while True:
                g = sub | lo

                # Internal constraint for one group (Gi,Gi): <= 1 edge inside
                if int_cnt[g] <= 1:
                    ok = True
                    for i in range(used):
                        if not compatible(g, groups[i]):
                            ok = False
                            break
                    if ok:
                        groups[used] = g
                        dfs(remaining ^ g, used + 1)
                        if found:
                            return

                if sub == 0:
                    break
                sub = (sub - 1) & rest  # next submask

        dfs((1 << n) - 1, 0)
        return found

    # Binary search for minimum K
    L, R = 1, n
    while L <= R:
        mid = (L + R) // 2
        if feasible(mid):
            R = mid - 1
        else:
            L = mid + 1

    # Output
    out_lines = [str(best_k)]
    for i in range(best_k):
        mask = best_groups[i]
        s = []
        for j in range(n):
            if (mask >> j) & 1:
                s.append(chr(97 + j))
        out_lines.append("".join(s))
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    solve()
```

This matches the intended editorial strategy: directed-graph reformulation, bitmask precomputation for constant-time checks, DFS with symmetry breaking, and binary search on the minimum number of buttons.
