Problem: Today is birthday of a Little Dasha — she is now 8 years old! On this occasion, each of her n friends and relatives gave her a ribbon with a greeting written on it, and, as it turned out, all the greetings are different. Dasha gathered all the ribbons and decided to throw away some of them in order to make the remaining set stylish. The birthday girl considers a set of ribbons stylish if no greeting written on some ribbon is a substring of another greeting written on some other ribbon. Let us recall that the substring of the string s is a continuous segment of s.

Help Dasha to keep as many ribbons as possible, so that she could brag about them to all of her friends. Dasha cannot rotate or flip ribbons, that is, each greeting can be read in a single way given in the input.

Input

The first line of the input contains integer n (1 ≤ n ≤ 750) — the number of Dasha's relatives and friends.

Each of the next n lines contains exactly one greeting. Each greeting consists of characters 'a' and 'b' only.

The total length of all greetings won't exceed 10 000 000 characters.

Output

In the first line print the maximum size of the stylish set. In the second line print the numbers of ribbons involved in it, assuming that they are numbered from 1 to n in the order they appear in the input. If there are several stylish sets of the maximum size, print any of them.

Examples

Input

5
abab
aba
aabab
ababb
bab


Output

2
2 5

Note

In the sample, the answer that keeps ribbons 3 and 4 is also considered correct.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <char MIN_CHAR = 'a', int ALPHABET = 26>
struct aho_corasick {
  struct node {
    int suff = -1, dict = -1, word_index = -1;
    int link[ALPHABET];
    node() { fill(link, link + ALPHABET, -1); }
    int &operator[](char c) { return link[c - MIN_CHAR]; }
  };
  int N, W;
  vector<node> nodes;
  vector<int> word_location;
  vector<int> word_indices_by_depth;
  vector<int> defer;
  aho_corasick(const vector<string> &words = {}) {
    if (!words.empty()) build(words);
  }
  vector<vector<int>> build_suffix_adj() const {
    vector<vector<int>> adj(N);
    for (int i = 1; i < N; i++) adj[nodes[i].suff].push_back(i);
    return adj;
  }
  int get_or_add_child(int current, char c) {
    if (nodes[current][c] >= 0) return nodes[current][c];
    return nodes[current][c] = N++;
  }
  int add_word(const string &word, int word_index) {
    assert(!nodes.empty());
    int current = 0;
    for (char c : word) current = get_or_add_child(current, c);
    if (nodes[current].word_index < 0) nodes[current].word_index = word_index;
    return current;
  }
  int get_suffix_link(int location, char c) const {
    if (location >= 0) location = nodes[location].link[c - MIN_CHAR];
    return max(location, 0);
  }
  void build(const vector<string> &words) {
    nodes.resize(1e7 + 5);
    N = 0;
    nodes[N++] = node();
    W = words.size();
    word_location.resize(W);
    defer.resize(W);
    int max_depth = 0;
    for (int i = 0; i < W; i++) {
      word_location[i] = add_word(words[i], i);
      max_depth = max(max_depth, (int)words[i].size());
      defer[i] = nodes[word_location[i]].word_index;
    }
    word_indices_by_depth.resize(words.size());
    vector<int> depth_freq(max_depth + 1, 0);
    for (int i = 0; i < (int)words.size(); i++) depth_freq[words[i].size()]++;
    for (int i = max_depth - 1; i >= 0; i--) depth_freq[i] += depth_freq[i + 1];
    for (int i = 0; i < (int)words.size(); i++)
      word_indices_by_depth[--depth_freq[words[i].size()]] = i;
    vector<int> q = {0};
    for (int i = 0; i < (int)q.size(); i++) {
      int current = q[i];
      for (char c = MIN_CHAR; c < MIN_CHAR + ALPHABET; c++) {
        int &index = nodes[current][c];
        if (index >= 0) {
          int suffix_parent = get_suffix_link(nodes[current].suff, c);
          nodes[index].suff = suffix_parent;
          nodes[index].dict = nodes[suffix_parent].word_index >= 0
                                  ? suffix_parent
                                  : nodes[suffix_parent].dict;
          q.push_back(index);
        } else {
          index = get_suffix_link(nodes[current].suff, c);
        }
      }
    }
  }
  vector<int> count_matches(const string &text) const {
    vector<int> matches(W, 0);
    int current = 0;
    for (char c : text) {
      current = get_suffix_link(current, c);
      int dict_node =
          nodes[current].word_index >= 0 ? current : nodes[current].dict;
      if (dict_node >= 0) matches[nodes[dict_node].word_index]++;
    }
    for (int word_index : word_indices_by_depth) {
      int location = word_location[word_index];
      int dict_node = nodes[location].dict;
      if (dict_node >= 0)
        matches[nodes[dict_node].word_index] += matches[word_index];
    }
    for (int i = 0; i < W; i++) matches[i] = matches[defer[i]];
    return matches;
  }
};
struct dinic_matching {
  static const int INF = 1e9 + 5;
  int N = -1, M = -1;
  vector<vector<int>> adj;
  vector<int> dist;
  vector<int> prev;
  vector<int> q;
  int q_start, q_end;
  vector<bool> matched;
  vector<int> edge_index;
  dinic_matching(int n = -1, int m = -1) {
    if (n >= 0 && m >= 0) init(n, m);
  }
  void init(int n, int m) {
    N = n;
    M = m;
    adj.assign(N, {});
    dist.resize(N);
    q.resize(N);
    matched.resize(N);
    edge_index.resize(N);
    prev.resize(M);
  }
  void add_edge(int a, int b) { adj[a].push_back(b); }
  bool bfs() {
    fill(dist.begin(), dist.end(), INF);
    q_start = q_end = 0;
    for (int i = 0; i < N; i++)
      if (!matched[i]) bfs_check(i, 0);
    bool has_path = false;
    while (q_start < q_end) {
      int num = q[q_start++];
      for (int next : adj[num])
        if (prev[next] < 0)
          has_path = true;
        else
          bfs_check(prev[next], dist[num] + 1);
    }
    return has_path;
  }
  void bfs_check(int num, int potential_dist) {
    if (potential_dist < dist[num]) {
      dist[num] = potential_dist;
      q[q_end++] = num;
    }
  }
  bool dfs(int num) {
    while (edge_index[num] < (int)adj[num].size()) {
      int next = adj[num][edge_index[num]];
      bool solved = false;
      if (prev[next] < 0 ||
          (dist[num] + 1 == dist[prev[next]] && dfs(prev[next]))) {
        prev[next] = num;
        matched[num] = true;
        solved = true;
      }
      edge_index[num]++;
      if (solved) return true;
    }
    dist[num] = INF;
    return false;
  }
  int match() {
    assert(N >= 0 && M >= 0);
    for (int i = 0; i < N; i++) matched[i] = false;
    for (int j = 0; j < M; j++) prev[j] = -1;
    int matches = 0;
    while (bfs()) {
      for (int i = 0; i < N; i++) edge_index[i] = 0;
      for (int i = 0; i < N; i++)
        if (!matched[i] && dfs(i)) matches++;
    }
    return matches;
  }
  vector<bool> reachable_left, reachable_right;
  void reachable_dfs(int left) {
    reachable_left[left] = true;
    for (int right : adj[left])
      if (prev[right] != left && !reachable_right[right]) {
        reachable_right[right] = true;
        int next_left = prev[right];
        if (next_left >= 0 && !reachable_left[next_left])
          reachable_dfs(next_left);
      }
  }
  vector<int> min_vertex_cover() {
    int size = match();
    reachable_left.assign(N, false);
    reachable_right.assign(M, false);
    for (int i = 0; i < N; i++)
      if (!matched[i] && !reachable_left[i]) reachable_dfs(i);
    vector<int> cover;
    for (int i = 0; i < N; i++)
      if (!reachable_left[i]) cover.push_back(i);
    for (int i = 0; i < M; i++)
      if (reachable_right[i]) cover.push_back(N + i);
    assert((int)cover.size() == size);
    return cover;
  }
  vector<int> max_independent_set() {
    int cover_size = min_vertex_cover().size();
    vector<int> independent_set;
    for (int i = 0; i < N; i++)
      if (reachable_left[i]) independent_set.push_back(i);
    for (int i = 0; i < M; i++)
      if (!reachable_right[i]) independent_set.push_back(N + i);
    assert((int)independent_set.size() == N + M - cover_size);
    return independent_set;
  }
};
int N;
vector<string> greetings;
aho_corasick<'a', 2> AC;
vector<vector<bool>> contains;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> N;
  greetings.resize(N);
  for (string &greeting : greetings) cin >> greeting;
  AC.build(greetings);
  contains.assign(N, vector<bool>(N, false));
  for (int i = 0; i < N; i++) {
    vector<int> matches = AC.count_matches(greetings[i]);
    for (int j = 0; j < N; j++) contains[i][j] = matches[j] > 0;
  }
  dinic_matching graph(N, N);
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      if (i != j && contains[i][j]) graph.add_edge(i, j);
  vector<int> vertex_cover = graph.min_vertex_cover();
  vector<bool> in_cover(N, false);
  for (int v : vertex_cover) in_cover[v % N] = true;
  vector<int> independent_set;
  for (int i = 0; i < N; i++)
    if (!in_cover[i]) independent_set.push_back(i);
  cout << independent_set.size() << '\n';
  for (int i = 0; i < (int)independent_set.size(); i++)
    cout << independent_set[i] + 1
         << (i < (int)independent_set.size() - 1 ? ' ' : '\n');
}