logo AlgoBeat OnlineJudge
登录 注册

#104075. [BZOJ 4075] [Wf2014]Game Strategy

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:无测试数据
上传者: 匿名

题目描述

Alice和Bob在玩一个游戏, 在平面上有n个域标号为a,b,c...,在游戏前Alice和Bob各自独立地选择一个域, 并把

刀片放在Bob的域然后游戏开始,每轮执行如下操作:

1.Alice在当前位置的可选的集合中选择一个集合S

2.Bob在S中选择一个不为当前位置的位置,把刀片移动到上面

若在某时刻刀片被放到了Alice的域上,游戏结束

由于Alice是一个抖M,她希望尽快迫使Bob把刀片放在Alice的域,而Bob则希望尽量晚.

输入格式

第一行一个整数n(n<=25)表示域的个数

接下来n行,每行有一个整数m(m<2^n,Σ m<=10^6),后跟m不同的字符串,以字典序给出,描述位置i的可选的集合

输出格式

输出一个n*n的矩阵

第i行第j个数表示,Bob初始选择第i个域,Alice初始选择第j个域,游戏最少要进行多少轮,如果无法给Alice寄

刀片则输出-1

样例

样例输入

2
2 ab b
1 b

样例输出

0 1 
-1 0