Problem: Today you are to solve the problem even the famous Hercule Poirot can't cope with! That's why this crime has not yet been solved and this story was never included in Agatha Christie's detective story books. 

You are not informed on what crime was committed, when and where the corpse was found and other details. We only know that the crime was committed in a house that has n rooms and m doors between the pairs of rooms. The house residents are very suspicious, that's why all the doors can be locked with keys and all the keys are different. According to the provided evidence on Thursday night all the doors in the house were locked, and it is known in what rooms were the residents, and what kind of keys had any one of them. The same is known for the Friday night, when all the doors were also locked. On Friday it was raining heavily, that's why nobody left the house and nobody entered it. During the day the house residents could

  * open and close doors to the neighboring rooms using the keys at their disposal (every door can be opened and closed from each side); 
  * move freely from a room to a room if a corresponding door is open; 
  * give keys to one another, being in one room. 



"Little grey matter" of Hercule Poirot are not capable of coping with such amount of information. Find out if the positions of people and keys on the Thursday night could result in the positions on Friday night, otherwise somebody among the witnesses is surely lying.

Input

The first line contains three preset integers n, m и k (1 ≤ n, m, k ≤ 1000) — the number of rooms, the number of doors and the number of house residents respectively. The next m lines contain pairs of room numbers which join the doors. The rooms are numbered with integers from 1 to n. There cannot be more that one door between the pair of rooms. No door connects a room with itself. The next k lines describe the residents' position on the first night. Every line contains a resident's name (a non-empty line consisting of no more than 10 Latin letters), then after a space follows the room number, then, after a space — the number of keys the resident has. Then follow written space-separated numbers of the doors that can be unlocked by these keys. The doors are numbered with integers from 1 to m in the order in which they are described in the input data. All the residents have different names, uppercase and lowercase letters considered to be different. Every m keys occurs exactly once in the description. Multiple people may be present in one room, some rooms may be empty. The next k lines describe the position of the residents on the second night in the very same format. It is guaranteed that in the second night's description the residents' names remain the same and every m keys occurs exactly once.

Output

Print "YES" (without quotes) if the second arrangement can result from the first one, otherwise, print "NO".

Examples

Input

2 1 2
1 2
Dmitry 1 1 1
Natalia 2 0
Natalia 1 1 1
Dmitry 2 0


Output

YES


Input

4 4 3
1 3
1 2
2 3
3 4
Artem 1 1 4
Dmitry 1 1 2
Edvard 4 2 1 3
Artem 2 0
Dmitry 1 0
Edvard 4 4 1 2 3 4


Output

NO

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
struct fastIO {
  inline fastIO operator>>(int& num) {
    num = 0;
    char c = getchar();
    while (c != '-' && (c < '0' || c > '9')) c = getchar();
    bool foo = 0;
    if (c == '-') {
      foo = 1;
      c = getchar();
    }
    while (c >= '0' && c <= '9') {
      num = (num << 3) + (num << 1) + c - '0';
      c = getchar();
    }
    if (foo) num = -num;
    return *this;
  }
  inline fastIO operator>>(long long& num) {
    num = 0;
    char c = getchar();
    while (c != '-' && (c < '0' || c > '9')) c = getchar();
    bool foo = 0;
    if (c == '-') {
      foo = 1;
      c = getchar();
    }
    while (c >= '0' && c <= '9') {
      num = (num << 3) + (num << 1) + c - '0';
      c = getchar();
    }
    if (foo) num = -num;
    return *this;
  }
  inline fastIO operator>>(float& num) {
    scanf("%f", &num);
    return *this;
  }
  inline fastIO operator>>(double& num) {
    scanf("%lf", &num);
    return *this;
  }
  inline fastIO operator>>(long double& num) {
    scanf("%Lf", &num);
    return *this;
  }
  inline fastIO operator>>(char& num) {
    num = getchar();
    while (num == ' ' || num == '\n') num = getchar();
    return *this;
  }
  inline fastIO operator>>(char* num) {
    int cnt = 0;
    char c = getchar();
    while (c == ' ' || c == '\n') c = getchar();
    while (c != ' ' && c != '\n') {
      num[cnt++] = c;
      c = getchar();
    }
    num[cnt] = 0;
    return *this;
  }
  inline fastIO operator>>(string& num) {
    cin >> num;
    return *this;
  }
  inline void printInt(const int& num) {
    if (num < 10) {
      putchar(num + '0');
      return;
    }
    printInt(num / 10);
    putchar((num % 10) + '0');
  }
  inline void printINT(const long long& num) {
    if (num < 10) {
      putchar(num + '0');
      return;
    }
    printINT(num / 10);
    putchar((num % 10) + '0');
  }
  inline fastIO operator<<(const int& num) {
    if (num < 0)
      putchar('-'), printInt(-num);
    else
      printInt(num);
    return *this;
  }
  inline fastIO operator<<(const long long& num) {
    if (num < 0)
      putchar('-'), printINT(-num);
    else
      printINT(num);
    return *this;
  }
  inline fastIO operator<<(const float& num) {
    printf("%.10f", num);
    return *this;
  }
  inline fastIO operator<<(const double& num) {
    printf("%.16lf", num);
    return *this;
  }
  inline fastIO operator<<(const long double& num) {
    printf("%.20Lf", num);
    return *this;
  }
  inline fastIO operator<<(const char& num) {
    putchar(num);
    return *this;
  }
  inline fastIO operator<<(const char* num) {
    for (int i = 0; num[i]; i++) putchar(num[i]);
    return *this;
  }
  inline fastIO operator<<(const string& num) {
    cout << num;
    return *this;
  }
} fio;
long long s2i(char* s) {
  long long ha = 0;
  for (int i = 0; s[i]; i++) {
    ha = ha * 19260817 + s[i];
  }
  return ha;
}
int n, m, k;
map<string, int> fff;
int FFF;
int a[1005], b[1005];
int Register(string s) {
  if (!fff.count(s)) {
    fff[s] = ++FFF;
  }
  return fff[s];
}
struct Dsu {
  int fa[1005];
  void init() {
    for (int i = 0; i < 1005; i++) {
      fa[i] = i;
    }
  }
  int root(int x) { return fa[x] == x ? x : (fa[x] = root(fa[x])); }
  void conn(int a, int b) {
    a = root(a);
    b = root(b);
    if (a == b) {
      return;
    }
    fa[a] = b;
  }
};
struct Room {
  bool hvkey[1005];
  bool hvprs[1005];
  bool operator<(const Room& rm) const {
    for (int i = 0; i < 1005; i++) {
      if (hvkey[i] != rm.hvkey[i]) {
        return hvkey[i] < rm.hvkey[i];
      }
    }
    return 0;
  }
  bool operator==(const Room& rm) const {
    for (int i = 0; i < 1005; i++) {
      if (hvkey[i] != rm.hvkey[i] || hvprs[i] != rm.hvprs[i]) {
        return 0;
      }
    }
    return 1;
  }
  void Debug() {
    for (int i = 1; i <= m; i++) {
      fio << hvkey[i] << ' ';
    }
    fio << '\n';
    for (int i = 1; i <= k; i++) {
      fio << hvprs[i] << ' ';
    }
    fio << '\n';
  }
};
struct State {
  Dsu dsu;
  Room room[1005];
  bool iskey(int rm, int ky) { return room[dsu.root(rm)].hvkey[ky]; }
  void addkey(int rm, int ky) { room[dsu.root(rm)].hvkey[ky] = 1; }
  void addprs(int rm, int pr) { room[dsu.root(rm)].hvprs[pr] = 1; }
  void Conn(int x, int y) {
    if (dsu.root(x) == dsu.root(y)) {
      return;
    }
    for (int i = 1; i <= k; i++) {
      room[dsu.root(y)].hvprs[i] |= room[dsu.root(x)].hvprs[i];
    }
    for (int i = 1; i <= m; i++) {
      room[dsu.root(y)].hvkey[i] |= room[dsu.root(x)].hvkey[i];
    }
    dsu.conn(x, y);
  }
  void Read() {
    for (int i = 0; i < k; i++) {
      string s;
      fio >> s;
      int prs = Register(s);
      int rm;
      fio >> rm;
      addprs(rm, prs);
      int keycnt;
      fio >> keycnt;
      while (keycnt--) {
        int key;
        fio >> key;
        addkey(rm, key);
      }
    }
  }
  bool mAKe() {
    bool changed = 0;
    for (int i = 1; i <= m; i++) {
      if ((dsu.root(a[i]) != dsu.root(b[i])) &&
          (iskey(a[i], i) || iskey(b[i], i))) {
        Conn(a[i], b[i]);
        changed = 1;
      }
    }
    return changed;
  }
  void Make() {
    while (mAKe())
      ;
  }
} bg, en;
vector<Room> stt, enn;
int main() {
  fio >> n >> m >> k;
  for (int i = 1; i <= m; i++) {
    fio >> a[i] >> b[i];
  }
  bg.dsu.init();
  en.dsu.init();
  bg.Read();
  en.Read();
  bg.Make();
  en.Make();
  for (int i = 1; i <= n; i++) {
    if (bg.dsu.root(i) == i) {
      stt.push_back(bg.room[i]);
    }
  }
  for (int i = 1; i <= n; i++) {
    if (en.dsu.root(i) == i) {
      enn.push_back(en.room[i]);
    }
  }
  sort((stt).begin(), (stt).end());
  sort((enn).begin(), (enn).end());
  fio << (stt == enn ? "YES" : "NO") << '\n';
  return 0;
}