#include using namespace std; template struct ModInt { int x; constexpr ModInt() : x(0) {} constexpr ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} constexpr ModInt &operator+=(const ModInt &p) noexcept { if ((x += p.x) >= mod) x -= mod; return *this; } constexpr ModInt &operator-=(const ModInt &p) noexcept { if ((x += mod - p.x) >= mod) x -= mod; return *this; } constexpr ModInt &operator*=(const ModInt &p) noexcept { x = (int)(1LL * x * p.x % mod); return *this; } constexpr ModInt &operator/=(const ModInt &p) noexcept { *this *= p.inverse(); return *this; } constexpr ModInt operator-() const { return ModInt(-x); } constexpr ModInt operator+(const ModInt &p) const noexcept { return ModInt(*this) += p; } constexpr ModInt operator-(const ModInt &p) const noexcept { return ModInt(*this) -= p; } constexpr ModInt operator*(const ModInt &p) const noexcept { return ModInt(*this) *= p; } constexpr ModInt operator/(const ModInt &p) const noexcept { return ModInt(*this) /= p; } constexpr bool operator==(const ModInt &p) const noexcept { return x == p.x; } constexpr bool operator!=(const ModInt &p) const noexcept { return x != p.x; } constexpr ModInt inverse() const noexcept { int a = x, b = mod, u = 1, v = 0, t = 0; while (b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return ModInt(u); } constexpr ModInt pow(int64_t n) const { ModInt res(1), mul(x); while (n) { if (n & 1) res *= mul; mul *= mul; n >>= 1; } return res; } friend constexpr ostream &operator<<(ostream &os, const ModInt &p) noexcept { return os << p.x; } friend constexpr istream &operator>>(istream &is, ModInt &a) noexcept { int64_t t = 0; is >> t; a = ModInt(t); return (is); } constexpr int get_mod() { return mod; } }; using mint = ModInt<>; template struct Matrix { vector> A; Matrix() {} Matrix(size_t m, size_t n) : A(m, vector(n, 0)) {} Matrix(size_t n) : A(n, vector(n, 0)) {} size_t height() const { return (A.size()); } size_t width() const { return (A[0].size()); } inline const vector &operator[](int k) const { return (A.at(k)); } inline vector &operator[](int k) { return (A.at(k)); } static Matrix E(size_t n) { Matrix mat(n); for (int i = 0; i < n; ++i) mat[i][i] = 1; return (mat); } Matrix &operator+=(const Matrix &B) { size_t m = height(), n = width(); assert(m == B.height() && n == B.width()); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) (*this)[i][j] += B[i][j]; return (*this); } Matrix &operator-=(const Matrix &B) { size_t m = height(), n = width(); assert(m == B.height() && n == B.width()); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) (*this)[i][j] -= B[i][j]; return (*this); } Matrix &operator*=(const Matrix &B) { size_t m = height(), n = B.width(), p = width(); assert(p == B.height()); vector> C(m, vector(n, 0)); for (int i = 0; i < m; ++i) for (int k = 0; k < p; ++k) { T tmp = (*this)[i][k]; for (int j = 0; j < n; ++j) C[i][j] += tmp * B[k][j]; } A.swap(C); return (*this); } Matrix &operator^=(long long k) { Matrix B = Matrix::E(height()); while (k) { if (k & 1) B *= *this; *this *= *this; k >>= 1; } A.swap(B.A); return (*this); } Matrix operator+(const Matrix &B) const { return (Matrix(*this) += B); } Matrix operator-(const Matrix &B) const { return (Matrix(*this) -= B); } Matrix operator*(const Matrix &B) const { return (Matrix(*this) *= B); } Matrix operator^(const long long k) const { return (Matrix(*this) ^= k); } Matrix trans() { size_t m = height(), n = width(); Matrix res(n, m); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) res[i][j] = (*this)[j][i]; return res; } Matrix inv() { assert(height() == width()); size_t n = height(); Matrix B(n, 2 * n); for (int i = 0; i < n; ++i) { B[i][i + n] = 1; for (int j = 0; j < n; ++j) B[i][j] = (*this)[i][j]; } for (int i = 0; i < n; ++i) { int piv = i; for (int j = i; j < n; ++j) if (abs(B[j][i]) > abs(B[piv][i])) piv = j; // not exist or unique assert(abs(B[piv][i]) >= 0); swap(B[i], B[piv]); for (int j = i + 1; j < 2 * n; ++j) B[i][j] /= B[i][i]; for (int j = 0; j < n; ++j) if (i != j) for (int k = i + 1; k < 2 * n; ++k) B[j][k] -= B[j][i] * B[i][k]; } Matrix res(n); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) res[i][j] = B[i][j + n]; return res; } T det() { int m = height(), n = width(); assert(m == n); T res = 1; Matrix B(m); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) B[i][j] = (*this)[i][j]; for (int i = 0; i < n; ++i) { int piv = i; for (int j = i + 1; j < m; ++j) if (B[j][i] != 0) { piv = j; break; } // if (abs(B[j][i]) > abs(B[piv][i])) piv = j; if (B[piv][i] == 0) return (T)0; // if (abs(B[piv][i]) < EPS) return (T)0; // B[piv][i] < EPS if (piv != i) swap(B[i], B[piv]), res = -res; res *= B[i][i]; // for (int j = i + 1; j < m; ++j) // for (int k = n - 1; k >= i; --k) B[j][k] -= B[i][k] * B[j][i] / // B[i][i]; { const T d = (T)1 / B[i][i]; for (int j = i + 1; j < n; ++j) B[i][j] *= d; for (int j = i + 1; j < m; ++j) for (int k = i + 1; k < n; ++k) B[j][k] -= B[i][k] * B[j][i]; } } return res; } friend ostream &operator<<(ostream &os, Matrix &p) { size_t m = p.height(), n = p.width(); for (int i = 0; i < m; i++) { os << "["; for (int j = 0; j < n; j++) { os << p[i][j] << (j + 1 == n ? "]\n" : ","); } } return (os); } }; // use Matrix, ModInt // MOD ver. #define MOD (long long)(2) int gauss_jordan(Matrix> &A, bool is_extended = false) { int m = A.height(), n = A.width(), rank = 0; for (int col = 0; col < n; ++col) { if (is_extended && col == n - 1) break; int piv = -1; for (int row = rank; row < m; ++row) if (A[row][col] != 0) { piv = row; break; } if (piv == -1) continue; swap(A[piv], A[rank]); ModInt inv = A[rank][col]; inv = inv.inverse(); for (int col2 = 0; col2 < n; ++col2) A[rank][col2] = A[rank][col2] * inv; for (int row = 0; row < m; ++row) if (row != rank && A[row][col] != 0) { ModInt fac = A[row][col]; for (int col2 = 0; col2 < n; ++col2) A[row][col2] -= A[rank][col2] * fac; } ++rank; } return rank; } int linear_equation(Matrix> A, vector> b, vector> &ans) { int m = A.height(), n = A.width(); Matrix> M(m, n + 1); assert((int)b.size() == m); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) M[i][j] = A[i][j]; M[i][n] = b[i]; } int rank = gauss_jordan(M, 1); ans.assign(n, 0); for (int i = 0; i < rank; ++i) ans[i] = M[i][n]; // exist? for (int row = rank; row < m; ++row) if (M[row][n] != 0) return -1; return rank; } int n, m; vector city, bits; vector solve(); int main() { cin >> n >> m; city.assign(m, 0); bits.assign(m, 0); for (int i = 0; i < m; ++i) { int len; cin >> len; while (len--) { int p; cin >> p; city[i] |= 1LL << --p; } cin >> bits[i]; } auto res = solve(); if (res.size()) for (auto p : res) cout << p << endl; else cout << -1 << endl; return 0; } vector solve() { vector res(n, 0); Matrix> A(m, n); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) A[i][j] = city[i] >> j & 1; for (int i = 0; i < 60; ++i) { vector> b(m), ans(n); for (int j = 0; j < m; ++j) b[j] = bits[j] >> i & 1; if (linear_equation(A, b, ans) < 0) return vector(); for (int j = 0; j < n; ++j) if (ans[j] == 1) res[j] |= 1LL << i; } for (int i = 0; i < m; ++i) { long long now = 0; for (int j = 0; j < n; ++j) if (city[i] >> j & 1) now ^= res[j]; if (now != bits[i]) return vector(); } return res; }