Dora the explorer has decided to use her money after several years of juicy royalties to go shopping. What better place to shop than Nlogonia?

There are $n$ stores numbered from $1$ to $n$ in Nlogonia. The $i$-th of these stores offers a positive integer $a_i$.

Each day among the last $m$ days Dora bought a single integer from some of the stores. The same day, Swiper the fox bought a single integer from all the stores that Dora did not buy an integer from on that day.

Dora considers Swiper to be her rival, and she considers that she beat Swiper on day $i$ if and only if the least common multiple of the numbers she bought on day $i$ is strictly greater than the least common multiple of the numbers that Swiper bought on day $i$.

The least common multiple (LCM) of a collection of integers is the smallest positive integer that is divisible by all the integers in the collection.

However, Dora forgot the values of $a_i$. Help Dora find out if there are positive integer values of $a_i$ such that she beat Swiper on every day. You don't need to find what are the possible values of $a_i$ though.

Note that it is possible for some values of $a_i$ to coincide in a solution.


-----Input-----

The first line contains integers $m$ and $n$ ($1\leq m \leq 50$, $1\leq n \leq 10^4$) — the number of days and the number of stores.

After this $m$ lines follow, the $i$-th line starts with an integer $s_i$ ($1\leq s_i \leq n-1$), the number of integers Dora bought on day $i$, followed by $s_i$ distinct integers, the indices of the stores where Dora bought an integer on the $i$-th day. The indices are between $1$ and $n$.


-----Output-----

Output must consist of a single line containing "possible" if there exist positive integers $a_i$ such that for each day the least common multiple of the integers bought by Dora is strictly greater than the least common multiple of the integers bought by Swiper on that day. Otherwise, print "impossible".

Note that you don't have to restore the integers themselves.


-----Examples-----
Input
2 5
3 1 2 3
3 3 4 5

Output
possible

Input
10 10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10

Output
impossible



-----Note-----

In the first sample, a possible choice for the values of the $a_i$ is $3, 4, 3, 5, 2$. On the first day, Dora buys the integers $3, 4$ and $3$, whose LCM is $12$, while Swiper buys integers $5$ and $2$, whose LCM is $10$. On the second day, Dora buys $3, 5$ and $2$, whose LCM is $30$, and Swiper buys integers $3$ and $4$, whose LCM is $12$.

Source: codeforces | Difficulty: HARD
Tags: Bit manipulation

Constructive algorithms

Complete search

Number theory

Mathematics


Solutions:
import math
(m, n) = list(map(int, input().split()))
days = []
for z in range(m):
	t = set(list(map(int, input().split()))[1:])
	days.append(t)
check = True
for i in range(m):
	for j in range(i):
		if not days[i].intersection(days[j]):
			check = False
			break
		if not check:
			break
if check:
	print('possible')
else:
	print('impossible')


(m, n) = map(int, input().split())
not_forbiden = []
result = 'possible'
for i in range(m):
	a = list(map(int, input().split()))
	n = a.pop(0)
	for forbes in not_forbiden:
		if all((elem not in a for elem in forbes)):
			result = 'impossible'
			break
	if result == 'impossible':
		break
	not_forbiden.append(a)
print(result)


import sys, math, queue, bisect
MOD = 10 ** 9 + 7
sys.setrecursionlimit(1000000)
(m, n) = map(int, input().split())
s = [None for i in range(m)]
for i in range(m):
	x = list(map(int, input().split()))
	s[i] = set(x[1:])
for i in range(m):
	for j in range(m):
		if s[i] & s[j] == set():
			print('impossible')
			exit()
print('possible')


(M, N) = map(int, input().split())
X = []
for i in range(M):
	X.append(set(list(map(int, input().split()))[1:]))
flg = 1
for i in range(M):
	for j in range(i):
		if len(X[i] & X[j]) == 0:
			flg = 0
			break
	if flg == 0:
		break
if flg:
	print('possible')
else:
	print('impossible')


(m, n) = [int(i) for i in input().split()]
mas = set(range(1, n + 1))
setd = []
sets = []
for i in range(m):
	s = set()
	[s.add(int(j)) for j in input().split()[1:]]
	setd.append(s)
	sets.append(mas.difference(s))
flag = True
for i in range(m):
	for j in range(m):
		if sets[i].issuperset(setd[j]):
			flag = False
			break
if flag:
	print('possible')
else:
	print('impossible')


(m, n) = map(int, input().split())
t = []
for i in range(m):
	temp = list(map(int, input().split()))[1:]
	bit = 0
	for i in temp:
		bit ^= 1 << i - 1
	t.append(bit)
ans = True
for i in range(m - 1):
	for j in range(i + 1, m):
		if t[i] & t[j] == 0:
			ans = False
print('possible' if ans else 'impossible')


(m, n) = list(map(int, input().split()))
s = [set([int(x) for x in input().split()][1:]) for _ in range(m)]
ok = True
for i in range(m):
	for j in range(i + 1, m):
		if not s[i] & s[j]:
			ok = False
			break
	if not ok:
		break
print(('' if ok else 'im') + 'possible')


(m, n) = list(map(int, input().split()))
s = [0] * m
for w in range(m):
	for i in list(map(int, input().split()))[1:]:
		s[w] |= 1 << i
for i in s:
	for j in s:
		if not i & j:
			print('impossible')
			return
print('possible')


from sys import stdin, stdout

def input():
	return stdin.readline()[:-1]
import math
(m, n) = list(map(int, input().split()))
days = []
for i in range(m):
	days.append(set(list(map(int, input().split()))[1:]))
possible = True
for i in range(m):
	for j in range(i):
		if not days[i].intersection(days[j]):
			possible = False
			break
	if not possible:
		break
if possible:
	print('possible')
else:
	print('impossible')


(m, n) = list(map(int, input().split()))
t = [set([i for i in list(map(int, input().split()))[1:]]) for _ in range(m)]
for i in range(m - 1):
	for j in range(i + 1, m):
		if len(t[i] & t[j]) == 0:
			print('impossible')
			break
	else:
		continue
	break
else:
	print('possible')


(m, n) = map(int, input().split())
b = [0] * m
for i in range(m):
	b[i] = list(map(int, input().split()))
	del b[i][0]
	b[i] = set(b[i])
flag = True
for i in b:
	for j in b:
		if i & j == set():
			flag = False
print('possible' if flag else 'impossible')


(m, n) = map(int, input().split())
sets = []
for i in range(m):
	a = list(map(int, input().split()))
	sets.append(set(a[1:]))
good = True
for i in range(m):
	for j in range(i + 1, m):
		if len(sets[i] & sets[j]) == 0:
			good = False
if good:
	print('possible')
else:
	print('impossible')


(m, n) = list(map(int, input().split()))
L = []
for i in range(0, m):
	s = [int(x) for x in input().split()]
	s = s[1:]
	L.append(set(s))
for i in range(m - 1):
	for j in range(i + 1, m):
		if len(L[i] & L[j]) == 0:
			print('impossible')
			break
	else:
		continue
	break
else:
	print('possible')


def push(d, x):
	if x not in d:
		d[x] = 0
	d[x] += 1

def check(a, i, j):
	for x in a[i]:
		d[x] += 1
	for x in a[j]:
		d[x] += 1
	for val in d:
		if val == 2:
			refresh()
			return True
	refresh()
	return False

def refresh():
	for i in range(len(d)):
		d[i] = 0
(m, n) = map(int, input().split())
d = [0] * 10010
arr = []
for _ in range(m):
	arr.append(list(map(int, input().split()))[1:])
flg = True
for i in range(m):
	for j in range(i + 1, m):
		if check(arr, i, j) == False:
			flg = False
			break
if flg == True:
	print('possible')
else:
	print('impossible')


inp = lambda cast=int: list(map(cast, input().split()))
printf = lambda s='', *args, **kwargs: print(str(s).format(*args), flush=True, **kwargs)
(m, n) = inp()
A = []
for _ in range(m):
	l = inp()
	A.append(set(l[1:]))
for i in range(m):
	for j in range(m):
		if i == j:
			continue
		if not A[i].intersection(A[j]):
			print('impossible')
			return
print('possible')


(m, n) = map(int, input().split())
s = set(range(1, n + 1))
d = [[None, None] for i in range(m)]
for i in range(m):
	x = list(map(int, input().split()))[1:]
	x = set(x)
	d[i][0] = x
	d[i][1] = s - x
for i in range(m):
	for j in range(i + 1, m):
		(bi, si) = d[i]
		(bj, sj) = d[j]
		if sj.issuperset(bi) and bj.issubset(si):
			print('impossible')
			quit()
print('possible')


(m, n) = map(int, input().split())
l = []
l = [list(map(int, input().split())) for i in range(m)]
l = [set(i[1:]) for i in l]
for i in range(m):
	for j in range(i + 1, m):
		if len(l[i].intersection(l[j])) == 0:
			print('impossible')
			return
print('possible')


import math
import re
import sys
from collections import defaultdict
from heapq import heappush, heappop
from fractions import gcd

def read(type=int):
	return type(input())

def read_list(type=int, split=' ', F=None):
	if F:
		return map(lambda x: F(type(x)), raw_input().split(split))
	return list(map(type, input().split(split)))

def read_list_of_list(N, type=int, split=' ', F=None):
	return [read_list(type, F=F) for _ in range(N)]
(m, n) = read_list()
B = read_list_of_list(m)
L = []
for b in B:
	b = set(b[1:])
	for l in L:
		if l.isdisjoint(b):
			print('impossible')
			exit()
	L += [b]
print('possible')


(m, n) = list(map(int, input().split()))
D = []
for i in range(m):
	A = list(map(int, input().split()))
	D.append(set(A[1:]))
for i in range(m):
	for j in range(i + 1, m):
		if D[i].intersection(D[j]) == set():
			print('impossible')
			return
print('possible')


def check(arr1, arr2):
	i1 = 0
	i2 = 0
	while True:
		if i1 == len(arr1) or i2 == len(arr2):
			return False
		elif arr1[i1] == arr2[i2]:
			return True
		elif arr1[i1] < arr2[i2]:
			i1 += 1
		else:
			i2 += 1
(m, n) = (int(x) for x in input().split())
day___set = []
for i in range(m):
	x = sorted([int(x) for x in input().split()][1:])
	day___set.append(x)
for i in range(m):
	for j in range(i + 1, m):
		if not check(day___set[i], day___set[j]):
			print('impossible')
			quit()
print('possible')


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
threading.stack_size(10 ** 8)
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
sys.setrecursionlimit(300000)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(m, n) = map(int, input().split())
l = []
for i in range(m):
	e = list(map(int, input().split()))
	l.append(set(e[1:]))
for i in range(m):
	for j in range(i + 1, m):
		if len(l[i] & l[j]) == 0:
			print('impossible')
			sys.exit(0)
print('possible')


import sys
input = sys.stdin.readline
(m, n) = map(int, input().split())
Dora = []
Swiper = []
all = set([i for i in range(1, n + 1)])
for _ in range(m):
	a = set(list(map(int, input().split()))[1:])
	Dora.append(a)
	Swiper.append(all.difference(a))
flag = 1
for i in range(m):
	for j in range(m):
		if Dora[i] | Swiper[j] == Swiper[j]:
			flag = 0
			break
	if flag == 0:
		break
if flag == 1:
	print('possible')
else:
	print('impossible')


(m, n) = list(map(int, input().split()))
a = [0] * m
for i in range(m):
	k = list(map(int, input().split()))
	for j in range(k[0]):
		a[i] |= 1 << k[j + 1]
for i in range(m):
	for j in range(m):
		if a[i] & a[j] == 0:
			print('impossible')
			quit()
print('possible')


import sys
input = sys.stdin.readline

def solve():
	(m, n) = map(int, input().split())
	c = [0] * (n + 1)
	a = [None] * m
	for i in range(m):
		s = map(int, input().split())
		next(s)
		a[i] = list(s)
	for i in range(m):
		for v in a[i]:
			c[v] += 1
		for j in range(i + 1, m):
			for v in a[j]:
				if c[v] > 0:
					break
			else:
				print('impossible')
				return
		for v in a[i]:
			c[v] -= 1
	print('possible')
solve()


(m, n) = map(int, input().split())
D = []
kok = {i for i in range(1, n + 1)}
for i in range(m):
	A = list(map(int, input().split()))
	D.append(set(A[1:]))
for i in range(m):
	for j in range(i + 1, m):
		if D[i].intersection(D[j]) == set():
			print('impossible')
			exit(0)
print('possible')


(m, n) = map(int, input().split())
t = [set([int(i) for i in input().split()][1:]) for j in range(m)]
for i in range(m - 1):
	for j in range(1, m):
		if not t[i] & t[j]:
			print('impossible')
			exit()
print('possible')


import sys
input = sys.stdin.readline
(m, n) = map(int, input().split())
D = [set(list(map(int, input().split()))[1:]) for i in range(m)]
for i in range(m - 1):
	for j in range(1, m):
		if D[i] & D[j] == set():
			print('impossible')
			sys.exit()
else:
	print('possible')


(m, n) = map(int, input().split())
l = [set(map(int, input().split()[1:])) for i in range(m)]
print(['', 'im'][any((not i & j for i in l for j in l))] + 'possible')


arr = input()
(M, N) = [int(x) for x in arr.split(' ')]
data = {}
for i in range(M):
	s = input()
	arr = [int(x) for x in s.split(' ')]
	arr = arr[1:]
	data[i] = set(arr)
ans = 1
for i in range(M):
	for j in range(i + 1, M):
		A = data[i]
		B = data[j]
		if len(A & B) == 0:
			ans = 0
if ans == 1:
	print('possible')
else:
	print('impossible')


import math
import sys
input = sys.stdin.readline
(m, n) = map(int, input().split())
a = []
for i in range(m):
	shops = tuple(map(lambda i: int(i) - 1, input().split()))
	a.append(shops[1:])
for i in range(m):
	for j in range(i):
		vis = [False] * n
		common = 0
		for k in a[i]:
			vis[k] = True
		for k in a[j]:
			common += vis[k]
		if common == 0:
			print('impossible')
			exit(0)
print('possible')


(m, n) = map(int, input().split())
cnt = [0] * (n + 1)
p = 1
arr = []
for _ in range(m):
	(*a,) = map(int, input().split())
	s = {a[i] for i in range(1, a[0] + 1)}
	for i in arr:
		if len(i | s) == len(i) + a[0]:
			print('impossible')
			exit()
	arr.append(s)
print('possible')


ii = lambda : int(input())
kk = lambda : map(int, input().split())
ll = lambda : list(kk())
(m, n) = kk()
ls = [kk() for _ in range(m)]
for l in ls:
	l.__next__()
ls = [set(s) for s in ls]
for i in range(m):
	for j in range(i + 1, m):
		if not ls[i] & ls[j]:
			print('impossible')
			exit()
print('possible')