#include #include #include #include #include #include using namespace std; struct Node { array child; int pass = 0; int term = 0; Node() { child.fill(-1); } }; struct TrieResult { vector trie; int n; }; TrieResult read_and_build(istream& in) { int n, m; in >> n >> m; vector trie; trie.reserve(500001); trie.emplace_back(); string s; for (int i = 0; i < n; ++i) { in >> s; int v = 0; ++trie[v].pass; for (char ch : s) { int c = ch - 'a'; int to = trie[v].child[c]; if (to == -1) { to = static_cast(trie.size()); trie[v].child[c] = to; trie.emplace_back(); } v = to; ++trie[v].pass; } ++trie[v].term; } return {move(trie), n}; } int minimum_comparable(const vector& trie) { struct Frame { int v, q; }; vector st; st.push_back({0, 0}); int best = INT_MAX; while (!st.empty()) { auto [v, q] = st.back(); st.pop_back(); if (v != 0) best = min(best, q + trie[v].pass); int q_child = q + trie[v].term; for (int c = 0; c < 26; ++c) { int to = trie[v].child[c]; if (to == -1) { // The root's missing child is also a valid nonempty X. best = min(best, q_child); } else { st.push_back({to, q_child}); } } } return best; } pair solve_trie(const vector& trie, int comparable_limit) { struct Frame { int v; int q; // number of input strings equal to proper prefixes of this node int next_child; // -1 before checking this node, otherwise next character to inspect }; vector st; st.reserve(trie.size()); st.push_back({0, 0, -1}); string path; path.reserve(trie.size()); while (!st.empty()) { Frame& f = st.back(); if (f.next_child == -1) { if (f.v != 0 && f.q + trie[f.v].pass <= comparable_limit) { return {true, path}; } f.next_child = 0; } const int child_q = f.q + trie[f.v].term; bool descended = false; while (f.next_child < 26) { const int c = f.next_child++; const int to = trie[f.v].child[c]; if (to == -1) { if (child_q <= comparable_limit) { string answer = path; answer.push_back(static_cast('a' + c)); return {true, move(answer)}; } } else { path.push_back(static_cast('a' + c)); st.push_back({to, child_q, -1}); descended = true; break; } } if (descended) continue; st.pop_back(); if (!st.empty()) path.pop_back(); } return {false, {}}; } int main(int argc, char** argv) { ios::sync_with_stdio(false); cin.tie(nullptr); bool print_min = false; if (argc >= 2 && string(argv[1]) == "--minimum-comparable") { print_min = true; } int n, m; if (!(cin >> n >> m)) return 0; vector trie; trie.reserve(500001); trie.emplace_back(); string s; for (int i = 0; i < n; ++i) { cin >> s; int v = 0; ++trie[v].pass; for (char ch : s) { int c = ch - 'a'; int& to = trie[v].child[c]; if (to == -1) { to = static_cast(trie.size()); trie.emplace_back(); } v = to; ++trie[v].pass; } ++trie[v].term; } if (print_min) { cout << minimum_comparable(trie) << '\n'; return 0; } const int comparable_limit = n - m; auto [ok, answer] = solve_trie(trie, comparable_limit); if (!ok) { cout << "No\n"; } else { cout << "Yes\n" << answer << '\n'; } }