Solution Notes (Travis Hance): Given a string s, we first look at what conditions we need such that s could possibly be lexicographically first. Compare s to any other string t. Suppose s and t first differ on the i^th character; that is, s[i] != t[i], but s[j] = t[j] for all j < i. Then, for s to be first lexicographically for some ordering of the alphabet, we would need s[i] to come before t[i] in that ordering.

Thus to determine if s could possibly be lexicographically first, we get a constraint of the form "character X must come before character Y in the ordering of the alphabet". (Although we need to be careful when s or t is a prefix of the other.) If we collect all these constraints, this reduces to checking if a graph is acyclic, where the graph has vertices corresponding to the letters of the alphabet. We can do this check in O((alphabet size)^2), where here, alphabet size = 26. We get one graph for each string, so once we have constructed all these graphs, we can finish in O(N * (alphabet size)^2)).

Thus we just need to figure out how to construct all N of these graphs efficiently. Naively, we can construct one such graph in time proportional to the total input size, but it is not nearly good enough to do that N times. The trick now is to first construct a trie on all the input strings. Note that for any string s, the graph for s depends only on the path from s to the root on the trie, and the children of any nodes on that path. Thus for any string, we can construct the corresponding graph simply by walking up the tree to the root and looking at the children as we walk up. For a string s of length l, this takes O(l * (alphabet size)). In total, this takes O(N * (alphabet size)), which is dominated by the time taken to do cyclicity testing.

Below is a solution contributed by Allen Chen that follows this approach.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<utility>
#include<cstring>
#include<stack>
#include<queue>

using namespace std;

typedef pair<int, int> pii;
typedef pair<int, pii> edge;

const int maxc = 26;
vector<string> vs;
vector<string> as;
int N;
int adj[maxc][maxc];
int deg[maxc];
struct node {
	node *child[maxc];
	bool is_end;
	node() {
		for (int i = 0; i < maxc; i++) child[i] = NULL;
		is_end = false;
	}
	void insert(string &s, int i, int id) {
		if (i == s.size()) {
			is_end = true;
			return;
		}
		int t = s[i] - 'a';
		if (child[t] == NULL) {
			//doesn't exist
			child[t] = new node(); // make a new node
		}
		child[t]->insert(s, i + 1, id);
	}
	bool dfs(string &s, int i) {
		if (i == s.size()) {
			return true;
		}
		if (is_end) return false;
		int t = s[i] - 'a';
		for (int j = 0; j < maxc; j++) {
			if (j != t && child[j] != NULL) {
				adj[t][j] = 1;
			}
		}
		return child[t]->dfs(s, i + 1);
	}
};
bool check() {
// if has cycle return false, else return true
	for (int i = 0; i < maxc; i++) {
		for (int j = 0; j < maxc; j++) {
			if (adj[i][j]) {
				deg[j]++; // incoming to node j
			}
		}
	}
	queue<int> q;
	for (int i = 0; i < maxc; i++) {
		if (deg[i] == 0) q.push(i);
	}
	int c = 0;
	while (q.size()) {
		int cur = q.front();
		q.pop();
		c++;
		for (int i = 0; i < maxc; i++) {
			if (adj[cur][i]) {
				deg[i]--;
				if (deg[i] == 0) q.push(i);
			}
		}
	}
	return c == maxc;
}
node *root = new node();
int main() {
	freopen("first.in", "r", stdin);
	freopen("first.out", "w", stdout);
	int ans = 0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		vs.push_back(s);
		root->insert(s, 0, i);
	}
	for (int i = 0; i < N; i++) {
		memset(adj, 0, sizeof(adj));
		memset(deg, 0, sizeof(deg));
		if (root->dfs(vs[i], 0) && check()) {
			ans++;
			as.push_back(vs[i]);
		}
	}
	cout << ans << '\n';
	for (int i = 0; i < ans; i++) {
		cout << as[i] << '\n';
	}

}