The LCMs Must be Large

题意翻译

题意 有一个长度为$n$（$n<=10^4$）的**内容未知**的序列，再给$m$（$m<=50$）个限制，每个限制会给一个位置集合$S$，需要让$S$中所有位置上的数的$lcm$严格大于序列里剩下的数的$lcm$，求是否存在一个这样的序列满足所有限制。 输入格式 第一行两个数$m,n$。 接下来$m$行，每行第一个整数$k$（$1<=k<n$）表示$S$的大小，接下来$k$个互不相同的整数描述这个位置集合$S$。 输出格式 如果存在一个序列输出 possible ，否则输出 impossible。

题目描述

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.

输入输出格式

输入格式

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 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.

输入输出样例

输入样例 #1

2 5
3 1 2 3
3 3 4 5

输出样例 #1

possible

输入样例 #2

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

输出样例 #2

impossible

说明

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 $ .