/* Written by Filip Hlasek 2016 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_FACES 200
#define MAX_VERTICES 200

struct Graph {

  int faces;
  int face[MAX_FACES][MAX_VERTICES];
  int face_degree[MAX_FACES];
  int face_size_low[MAX_FACES], face_size_high[MAX_FACES];

  int black_vertices, white_vertices;
  int incident_face[2 * MAX_VERTICES][MAX_FACES];
  int vertex_degree[2 * MAX_VERTICES]; // Equals number of incident faces

  int face_id_in_coloring[MAX_FACES];

  void read_description(Graph *contracted_version = NULL) {
    scanf("%d%d", &faces, &white_vertices);
    for (int i = 0; i < white_vertices; ++i) {
      vertex_degree[i] = 0;
    }
    black_vertices = 0;
    for (int face_id = 0; face_id < faces; ++face_id) {
      char buffer[3 * MAX_VERTICES];

      face_id_in_coloring[face_id] = face_id;

      if (contracted_version != NULL) {
        int id;
        scanf("%d", &id);
        if (!id) {
          face_size_low[face_id] = face_size_high[face_id] = 0;
        }
        else {
          --id;
          face_size_low[face_id] = contracted_version->face_size_low[id];
          face_size_high[face_id] = contracted_version->face_size_high[id];
          face_id_in_coloring[face_id] = id;
        }
      }
      else {
        scanf("%s", buffer);
        int buffer_len = strlen(buffer);
        int low = -1, num = 0;
        for (int i = 0; i < buffer_len; ++i) {
          if (buffer[i] == '-') {
            low = num;
            num = 0;
          }
          else {
            num = 10 * num + buffer[i] - '0';
          }
        }
        if (low == -1) {
          low = num;
        }
        face_size_low[face_id] = low;
        face_size_high[face_id] = num;
      }

      face_degree[face_id] = 0;

      scanf("%s", buffer);
      int buffer_len = strlen(buffer);
      for (int i = 0; i < buffer_len; ++i) {
        if (buffer[i] == '-' || buffer[i] == '0') {
          continue;
        }
        int id = black_vertex_id(buffer[i] - 'a');
        face[face_id][face_degree[face_id]++] = id;
        while (black_vertices <= buffer[i] - 'a') {
          vertex_degree[black_vertex_id(black_vertices++)] = 0;
        }
        incident_face[id][vertex_degree[id]++] = face_id;
      }

      if (contracted_version == NULL && face_size_high[face_id]) {
        face_size_low[face_id] -= face_degree[face_id];
        face_size_high[face_id] -= face_degree[face_id];
      }

      scanf("%s", buffer);
      buffer_len = strlen(buffer);
      buffer[buffer_len] = ',';
      int id = 0;
      for (int i = 0; i <= buffer_len; ++i) {
        if (buffer[i] == ',') {
          id--;
          face[face_id][face_degree[face_id]++] = id;
          incident_face[id][vertex_degree[id]++] = face_id;
          id = 0;
        }
        else {
          id = 10 * id + buffer[i] - '0';
        }
      }
    }
  }

  // Returns id of black vertex in the coloring.
  int black_vertex_id(int vertex_id) {
    return MAX_VERTICES + vertex_id;
  }

  int outer_vertex_id(int face_id, int vertex) {
    return MAX_VERTICES * (2 + face_id) + vertex;
  }

  /**
   * It prints (in this order): black vetices, white vertices, outer vertices.
   */
  void print_coloring(int coloring[]) {
    for (int i = 0; i < black_vertices; ++i) {
      printf("%c", coloring[black_vertex_id(i)] + 'A' - 1);
    }
    printf(" ");
    for (int i = 0; i < white_vertices; ++i) {
      printf("%c", coloring[i] + 'A' - 1);
    }
    for (int face_id = 0; face_id < faces; ++face_id) {
      printf(" [");
      for (int vertex = 0; vertex < face_size_high[face_id]; ++vertex) {
        printf("%c", coloring[outer_vertex_id(face_id, vertex)] + 'A' - 1);
      }
      printf("]");
    }
    printf("\n");
  }

  // Returns true if all colorings are fine.
  bool color_black_vertices(int coloring[], int vertex_id, int colors_used) {

    // All black vertices have been colored.
    if (vertex_id == black_vertex_id(black_vertices)) {
      /*
      for (int i = 0; i < black_vertices; ++i) {
        printf("%c", coloring[black_vertex_id(i)] + 'A' - 1);
      }
      printf("\n");
      */
      outer_vertices_coloring_counter = 0;
      white_colorable = 0;
      bool ans = color_outer_vertices(coloring, 0, 0, 1, colors_used);
      total_colorings += outer_vertices_coloring_counter;
      total_white_colorable += white_colorable;
      // printf("%lld / %lld\n", white_colorable, outer_vertices_coloring_counter);
      return ans;
    }

    for (int color = 1; color <= colors_used; ++color) {
      bool valid = true;
      // The only condition for the color is that it must be different from
      // colors of all vertices on the same faces.
      for (int i = 0; i < vertex_degree[vertex_id]; ++i) {
        int face_id = incident_face[vertex_id][i];
        for (int j = 0; j < face_degree[face_id]; ++j) {
          int vertex = face[face_id][j];
          if (vertex < white_vertices) break;
          if (coloring[vertex] == color) {
            valid = false;
            break;
          }
        }
        if (!valid) {
          break;
        }
      }
      if (!valid) continue;
      coloring[vertex_id] = color;
      if (!color_black_vertices(coloring, vertex_id + 1, colors_used)) {
        coloring[vertex_id] = 0;
        return false;
      }

      coloring[vertex_id] = 0;
    }

    // Completely new color can be assigned to this vertex as well.
    coloring[vertex_id] = colors_used + 1;
    if (!color_black_vertices(coloring, vertex_id + 1, colors_used + 1)) {
      coloring[vertex_id] = 0;
      return false;
    }

    coloring[vertex_id] = 0;
    return true;
  }

  long long outer_vertices_coloring_counter, white_colorable;

  Graph *decontracted;

  /**
   * There can be many outer vertices and that's why we don't pick colors
   * For them, but rather these colors that are missing among them.
   * (Except for black vertices on that faces, which have a color already).
   * Given the partial coloring, it is looking for all nonisomorphic colorings
   * of outer vertices.
   *
   * Returns true if all the coloring which can be extended in the contracted
   * graph, can be extended in the original graph as well.
   */
  bool color_outer_vertices(
    int coloring[], int face_id, int vertex, int min_color, int colors_used
  ) {

    // A coloring has been found.
    if (face_id == faces) {
      // This counter is not important for the algorithm and is here only
      // for debugging purposes.
      outer_vertices_coloring_counter++;
      // If the coloring can be extended in the contracted graph.
      if (color_white_vertices(coloring, 0)) {
        white_colorable++;
        // Test if it can be extended in the original graph.
        if (!decontracted->color_white_vertices(coloring, 0)) {
          printf("Counterexample:\n");
          print_coloring(coloring);
          return false;
        }
      }
      return true;
    }

    // Outer vertices of the current face have all been colored, let's
    // color the next face.
    if (vertex >= face_size_low[face_id]) {
      if (!color_outer_vertices(coloring, face_id + 1, 0, 1, colors_used)) {
        return false;
      }
    }

    if (vertex == face_size_high[face_id]) {
      return true;
    }

    int id = outer_vertex_id(face_id, vertex);

    // Maximum color assigned to a black vertex.
    // All other colors are isomorphic iff they are contained in the same
    // set of outer faces.
    int max_black_color = 0;
    for (int i = 0; i < black_vertices; ++i) {
      if (coloring[black_vertex_id(i)] > max_black_color) {
        max_black_color = coloring[black_vertex_id(i)];
      }
    }

    // There are face_size[face_id] on that face.
    // We are looing for one of them.
    // We can either take one of the already used colors or take a new one.
    for (int color = min_color; color <= colors_used; ++color) {
      bool valid = true;
      // It is not a valid color if any black vertex on that face has it.
      for (int j = 0; j < face_degree[face_id]; ++j) {
        int vertex = face[face_id][j];
        if (vertex < white_vertices) break;
        if (coloring[vertex] == color) {
          valid = false;
          break;
        }
      }
      if (!valid) {
        continue;
      }
      // It is not a valid color it it is isomorphic with any smaller one.
      for (int other_color = min_color; other_color < color; ++other_color) {
        if (other_color <= max_black_color) {
          continue;
        }
        bool isomorphic = true;
        // Two colors are isomorphic if they are contained in the same set
        // of faces and are not at any black vertex.
        for (int face_id = 0; face_id < faces; ++face_id) {
          bool color_present = false, other_color_present = false;
          for (int i = 0; i < face_size_high[face_id]; ++i) {
            int c = coloring[outer_vertex_id(face_id, i)];
            if (color == c) {
              color_present = true;
            }
            if (other_color == c) {
              other_color_present = true;
            }
          }
          if (color_present != other_color_present) {
            isomorphic = false;
            break;
          }
        }

        if (isomorphic) {
          valid = false;
          break;
        }
      }
      if (!valid) {
        continue;
      }
      // It is valid to use that color.
      coloring[id] = color;
      if (!color_outer_vertices(
        coloring, face_id, vertex + 1, color + 1, colors_used
      )) {
        coloring[id] = 0;
        return false;
      }

      coloring[id] = 0;
    }

    // We can also use a new color to color that vertex.
    coloring[id] = colors_used + 1;
    if (!color_outer_vertices(
      coloring, face_id, vertex + 1, colors_used + 2, colors_used + 1
    )) {
      coloring[id] = 0;
      return false;
    }

    coloring[id] = 0;
    return true;
  }

  /**
   * Given the coloring of black vertices and outer vertices, looking
   * for any valid coloring of white vertices recursively.
   */
  bool color_white_vertices(int coloring[], int vertex_id) {

    // All white vertices have been successfuly colored.
    if (vertex_id == white_vertices) {
      return true;
    }

    // Looking for a neighboring face, which contains outer vertices
    // - if no such a face exists, this vertex can be colored arbitrarily.
    for (int i = 0; i < vertex_degree[vertex_id]; ++i) {
      int face_id = incident_face[vertex_id][i];
      if (face_size_high[face_id]) {
        // Neighboring face with outer vertices has been found.
        // This vertex can only be assigned these colors that are missing
        // at that face.
        for (int vertex = 0; vertex < face_size_high[face_id]; ++vertex) {
          // Possible color for the current vertex - still need to test it.
          int face_coloring_id = face_id_in_coloring[face_id];
          int id_in_coloring = outer_vertex_id(face_coloring_id, vertex);
          int color = coloring[id_in_coloring];
          if (!color) {
            continue;
          }
          bool valid = true;
          // It might not be valid if any other neighboring face forbids it.
          for (int j = i + 1; j < vertex_degree[vertex_id]; ++j) {
            int face2_id = incident_face[vertex_id][j];
            int vertices = face_size_high[face2_id];
            // Only these faces, which contains outer vertices.
            if (vertices) {
              bool contains = false;
              // Is the color in missing colors list of that face?
              for (int vertex2 = 0; vertex2 < vertices; ++vertex2) {
                int face_coloring_id = face_id_in_coloring[face2_id];
                int id_in_coloring = outer_vertex_id(face_coloring_id, vertex2);
                if (coloring[id_in_coloring] == color) {
                  contains = true;
                  break;
                }
              }
              // The color is already at that face (not contained in the list)..
              if (!contains) {
                valid = false;
                break;
              }
            }
          }
          // Other possibility is that some inner neighboring vertex
          // (black or white) has this color already.
          for (int j = 0; j < vertex_degree[vertex_id]; ++j) {
            if (!valid) {
              break;
            }
            int face2_id = incident_face[vertex_id][j];
            for (int k = 0; k < face_degree[face2_id]; ++k) {
              if (coloring[face[face2_id][k]] == color) {
                valid = false;
                break;
              }
            }
          }

          // The color can be assigned to the vertex. Let's try it.
          if (valid) {
            coloring[vertex_id] = color;
            // Try if the rest of the graph can be colored.
            if (color_white_vertices(coloring, vertex_id + 1)) {
              coloring[vertex_id] = 0;
              return true;
            }
            coloring[vertex_id] = 0;
          }
        }
        return false;
      }
    }

    return color_white_vertices(coloring, vertex_id + 1);
  }

  long long total_colorings, total_white_colorable;

  /**
   * A coloring consists of
   *   0                .. MAX_VERTICES - 1      : black vertices (letters)
   *   MAX_VERTICES     .. 2 * MAX_VERTICES - 1  : white vertices (numbers)
   *   2 * MAX_VERTICES .. 3 * MAX_VERTICES - 1  : face 1 outer vertices
   *   3 * MAX_VERTICES .. 4 * MAX_VERTICES - 1  : face 2 outer vertices
   *   ...              .. ...
   */
  int coloring[2 * MAX_VERTICES + MAX_FACES * MAX_VERTICES];
  /**
   * Returns true if all colorings of black and outer vertices,
   * which can be extended to color white vertices, can be extended to white
   * vertices in the decontracted graph as well.
   */
  bool test_all_colorings(Graph *_decontracted) {
    for (int i = 0; i < MAX_VERTICES * (2 + faces); ++i) {
      coloring[i] = 0;
    }
    total_colorings = total_white_colorable = 0;
    decontracted = _decontracted;
    bool ans = color_black_vertices(coloring, black_vertex_id(0), 0);
    printf(
      "The total number of colorings: %lld\nThe number of extendable colorings: %lld\n",
      total_colorings, total_white_colorable
    );
    return ans;
  }

};

int main(int argc, char **argv) {
  Graph contracted, g;
  contracted.read_description();
  g.read_description(&contracted);
  if (contracted.test_all_colorings(&g)) {
    printf("OK\n");
  }
  else {
    printf("INVALID\n");
  }
  return (0);
}