Hunting for Treasure

题目描述

You're playing a game.

The game consists of $n$ boss battles, indexed $1\dots n$. The battles can be completed in any order, but any battle can only be completed once. There are $m$ possible rewards for completing a battle, indexed $1\dots m$. However, not all rewards can be obtained by completing any battle. For each battle $i$, there is a list of possible rewards $A_i = [a_{i1},a_{i2} \dots a_{ik}]$. You can only get rewards in $A_{i}$ after you have completed battle $i$.Additionally, once you have obtained a given reward, you cannot obtain it again.

When you complete battle $i$, you will receive one of rewards from $A_i$ that you have not yet received, at random. If you have already obtained all possible rewards from battle $i$, you get nothing.

You want to find out which rewards you can guarantee obtaining. Your task is to, for each $i= 1\dots m$ independently, find out if there is a strategy that guarantees you will receive reward $i$.

输入格式

The first line contains one integer $t$ $(1 \le t \le 1000)$ —the number of test cases. Each test case is described as follows.

The first line contains two integers $n$ and $m$ $(1 \le n, m \le 250)$ — the number of battles and rewards,respectively.

The next $n$ lines describe the possible rewards for completing battles.

The $i$-th line starts with an integer $k_i$ $(0 \le k_i \le m)$,followed by $k_i$ integers $a_{i1}, a_{i2}, \ldots, a_{ik_i}$ $(1 \le a_{i1} \lt a_{i2} \lt \cdots \lt a_{ik_i} \le m)$ —the possible rewards for completing battle $i$.

It is guaranteed that the sum of $\sum_{i=1}^{n} k_i$ over all test cases doesn't exceed $10^5$.

输出格式

For each test case, print a binary string of length $m$. The $i$-th character should be 1 if it is possible to guarantee obtaining reward $i$, and 0 otherwise.

样例输入 #1

2
4 4
2 1 2
2 2 3
2 2 3
1 3
5 5
1 4
2 1 3
2 4 5
2 2 4
1 5

样例输出 #1

1110
01011