#include <bits/stdc++.h>
using namespace std;
const int prime = 1000000009;
int n, m;
int d[60][60], l[60][60], r[60][60], vis[100000];
bool con[60][60];
void init() {
  scanf("%d%d", &n, &m);
  memset(d, 0, sizeof(d));
  memset(con, false, sizeof(con));
  memset(vis, 0, sizeof(vis));
  int top = 0;
  int i, j;
  for (i = 1; i <= (m); ++i) {
    int x, y, z, t;
    scanf("%d%d%d", &x, &y, &z);
    d[x][y] = z;
    con[x][y] = true;
    l[x][y] = top + 1;
    r[x][y] = top + z;
    for (j = 1; j <= (z); ++j) {
      scanf("%d", &t);
      vis[top + j] = t;
    }
    top += z;
  }
}
int ql, qr;
int q[1000];
void goback() {
  while (ql <= qr && qr <= 2 * n + 2) {
    int y = q[ql - 1];
    int x = q[ql++];
    if (!con[x][y]) {
      qr = ql + 1;
      return;
    }
    for (int p = r[x][y]; p >= l[x][y]; --p) q[++qr] = vis[p];
  }
}
void gofront() {
  while (ql <= qr && qr <= 2 * n + 2) {
    int x = q[ql - 1];
    int y = q[ql++];
    if (!con[x][y]) {
      qr = ql + 1;
      return;
    }
    for (int p = l[x][y]; p <= r[x][y]; ++p) q[++qr] = vis[p];
  }
}
int fullpath[60][60][120], prefix[60][60][120], suffix[60][60][120];
int allpre[120][60], allsuf[120][60], preandmid[120][60];
int ans[60];
void work() {
  int i, j, k, len;
  memset(fullpath, 0, sizeof(fullpath));
  memset(prefix, 0, sizeof(prefix));
  memset(suffix, 0, sizeof(suffix));
  for (i = 1; i <= (n); ++i)
    for (j = 1; j <= (n); ++j)
      for (k = l[i][j]; k <= (r[i][j] - 1); ++k)
        if (vis[k] == i && vis[k + 1] == j) {
          int len = 0;
          ql = 2;
          qr = 0;
          for (int p = k; p >= l[i][j]; --p) q[++qr] = vis[p];
          goback();
          int x = q[qr];
          len += qr;
          if (ql <= qr) continue;
          ql = 2;
          qr = 0;
          for (int p = k + 1; p <= r[i][j]; ++p) q[++qr] = vis[p];
          gofront();
          int y = q[qr];
          len += qr;
          if (ql <= qr) continue;
          fullpath[x][y][len]++;
        }
  for (i = 1; i <= (n); ++i)
    for (j = 1; j <= (n); ++j)
      if (vis[r[i][j]] == i) {
        int len = 0;
        ql = 2;
        qr = 0;
        for (int p = r[i][j]; p >= l[i][j]; --p) q[++qr] = vis[p];
        goback();
        int x = q[qr];
        len += qr;
        if (ql <= qr) continue;
        prefix[x][j][len]++;
      }
  for (i = 1; i <= (n); ++i)
    for (j = 1; j <= (n); ++j)
      if (vis[l[i][j]] == j) {
        int len = 0;
        ql = 2;
        qr = 0;
        for (int p = l[i][j]; p <= r[i][j]; ++p) q[++qr] = vis[p];
        gofront();
        int y = q[qr];
        len += qr;
        if (ql <= qr) continue;
        suffix[i][y][len]++;
      }
  memset(allpre, 0, sizeof(allpre));
  memset(allsuf, 0, sizeof(allsuf));
  for (i = 1; i <= (n); ++i) allpre[0][i] = allsuf[0][i] = 1;
  for (i = 1; i <= (2 * n + 1); ++i)
    for (j = 1; j <= (n); ++j)
      for (k = 1; k <= (n); ++k)
        for (len = 1; len <= (i); ++len)
          allpre[i][j] = (allpre[i][j] +
                          (long long)prefix[k][j][len] * allpre[i - len][k]) %
                         prime;
  for (i = 1; i <= (2 * n + 1); ++i)
    for (j = 1; j <= (n); ++j)
      for (k = 1; k <= (n); ++k)
        for (len = 1; len <= (i); ++len)
          allsuf[i][j] = (allsuf[i][j] +
                          (long long)suffix[j][k][len] * allsuf[i - len][k]) %
                         prime;
  memset(preandmid, 0, sizeof(preandmid));
  for (i = 1; i <= (2 * n + 1); ++i)
    for (j = 1; j <= (n); ++j)
      for (k = 1; k <= (n); ++k)
        for (len = 1; len <= (i); ++len)
          preandmid[i][j] = (preandmid[i][j] + (long long)fullpath[k][j][len] *
                                                   allpre[i - len][k]) %
                            prime;
  memset(ans, 0, sizeof(ans));
  for (i = 1; i <= (2 * n + 1); ++i)
    for (j = 1; j <= (n); ++j)
      for (len = 1; len <= (i); ++len)
        ans[i] = (ans[i] + (long long)preandmid[len][j] * allsuf[i - len][j]) %
                 prime;
  for (i = 1; i <= (2 * n); ++i) printf("%d\n", ans[i + 1]);
}
int main() {
  init();
  work();
  return 0;
}
