Problem: Welcome to the world of Pokermon, yellow little mouse-like creatures, who absolutely love playing poker! 

Yeah, right… 

In the ensuing Pokermon League, there are n registered Pokermon trainers, and t existing trainer teams each of which belongs to one of two conferences. Since there is a lot of jealousy between trainers, there are e pairs of trainers who hate each other. Their hate is mutual, there are no identical pairs among these, and no trainer hates himself (the world of Pokermon is a joyful place!). Each trainer has a wish-list of length li of teams he’d like to join.

Your task is to divide players into teams and the teams into two conferences, so that: 

  * each trainer belongs to exactly one team; 
  * no team is in both conferences; 
  * total hate between conferences is at least e / 2; 
  * every trainer is in a team from his wish-list. 



Total hate between conferences is calculated as the number of pairs of trainers from teams from different conferences who hate each other. 

Input

The first line of the input contains two integer n (4 ≤ n ≤ 50 000) and e (2 ≤ e ≤ 100 000) — the total number of Pokermon trainers and the number of pairs of trainers who hate each other.

Pokermon trainers are numbered from 1 to n. Next e lines contain two integers a and b (1 ≤ a, b ≤ n) indicating that Pokermon trainers a and b hate each other. Next 2n lines are in a following format. Starting with Pokermon trainer 1, for each trainer in consecutive order: first number li (16 ≤ li ≤ 20) — a size of Pokermon trainers wish list, then li positive integers ti, j (1 ≤ ti, j ≤ T), providing the teams the i-th trainer would like to be on.

Each trainers wish list will contain each team no more than once. Teams on the wish lists are numbered in such a way that the set of all teams that appear on at least 1 wish list is set of consecutive positive integers {1, 2, 3, …, T}. Here T might be up to 1 000 000.

Output

Print two lines. The first line should contain n numbers, specifying for each trainer the team he is in.

The second line should contain T numbers, specifying the conference for each team (1 or 2).

Example

Input

4 3
1 2
2 3
4 1
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 15
16
2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 18
16
2 3 4 5 6 7 8 9 10 11 12 13 14 15 18 19
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 19


Output

16 15 19 14 
2 2 2 1 1 1 2 1 1 2 1 1 1 2 2 1 1 1 1 

Note

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <class T1, class T2>
std::ostream& operator<<(std::ostream& os, const pair<T1, T2>& p) {
  os << "[" << p.first << ", " << p.second << "]";
  return os;
}
template <class T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  os << "[";
  bool first = true;
  for (typename std::vector<T>::const_iterator it = v.begin(); it != v.end();
       ++it) {
    if (!first) os << ", ";
    first = false;
    os << *it;
  }
  os << "]";
  return os;
}
vector<string> _split(const string& s, char c) {
  vector<string> v;
  stringstream ss(s);
  string x;
  while (getline(ss, x, c)) v.emplace_back(x);
  return v;
}
void _print(vector<string>::iterator) {}
template <typename T, typename... Args>
void _print(vector<string>::iterator it, T a, Args... args) {
  string name = it->substr((*it)[0] == ' ', it->length());
  if (isalpha(name[0]))
    cerr << name << " = " << a << " ";
  else
    cerr << name << " ";
  _print(++it, args...);
}
const int N = 1001001;
int n, e;
int a[N], b[N];
vector<int> g[N];
int T;
vector<int> cand[N];
vector<int> order;
int ans_team[N], ans_conf[N];
int team[N], conf[N];
vector<int> contestant_list[N];
int main() {
  scanf("%d", &n);
  scanf("%d", &e);
  for (int i = 1; i <= e; i++) {
    scanf("%d", &a[i]);
    scanf("%d", &b[i]);
    g[a[i]].push_back(b[i]);
    g[b[i]].push_back(a[i]);
  }
  for (int i = 1; i <= n; i++) {
    int cnt;
    scanf("%d", &cnt);
    for (int j = 0; j < cnt; j++) {
      int val;
      scanf("%d", &val);
      T = max(T, val);
      cand[i].push_back(val);
    }
  }
  while (true) {
    for (int i = 1; i <= T; i++) {
      contestant_list[i].clear();
    }
    for (int i = 1; i <= n; i++) {
      team[i] = rand() % (cand[i].size());
      team[i] = cand[i][team[i]];
      contestant_list[team[i]].push_back(i);
    }
    order.clear();
    for (int i = 1; i <= T; i++) {
      order.push_back(i);
    }
    random_shuffle(order.begin(), order.end());
    for (int i = 1; i <= T; i++) {
      conf[i] = 0;
    }
    for (int i = 0; i < order.size(); i++) {
      int id = order[i];
      int cnt1 = 0;
      int cnt2 = 0;
      for (int j = 0; j < contestant_list[id].size(); j++) {
        int contestant_id = contestant_list[id][j];
        for (int q = 0; q < g[contestant_id].size(); q++) {
          int other = g[contestant_id][q];
          int other_team = team[other];
          if (conf[other_team] == 0) continue;
          if (conf[other_team] == 1)
            cnt1++;
          else
            cnt2++;
        }
      }
      if (cnt1 > cnt2) {
        conf[id] = 2;
      } else if (cnt1 < cnt2) {
        conf[id] = 1;
      } else {
        conf[id] = rand() % 2 + 1;
      }
    }
    int good_edges = 0;
    for (int i = 1; i <= e; i++) {
      int g1 = conf[team[a[i]]];
      int g2 = conf[team[b[i]]];
      if (g1 != g2) good_edges++;
    }
    if (good_edges * 2 < e) continue;
    for (int i = 1; i <= n; i++) {
      ans_team[i] = team[i];
    }
    for (int i = 1; i <= T; i++) {
      ans_conf[i] = conf[i];
    }
    break;
  }
  for (int i = 1; i <= n; i++) {
    if (i > 1) printf(" ");
    printf("%d", ans_team[i]);
  }
  puts("");
  for (int i = 1; i <= T; i++) {
    if (i > 1) printf(" ");
    printf("%d", ans_conf[i]);
  }
  puts("");
  return 0;
}