T2

题目描述

小王bot进群后和群友玩起了一个 “传炸弹” 的游戏。

群内包括小王bot在内的 $n$ 个人中每个人都对所有人（包括自己）有一个仇恨值，用矩阵 $a$ 表示。

其中，第 $i$ 个人对第 $j$ 个人的仇恨值为 $a_{i,j}$

保证对于所有 $i$ ，$a_{i,1}$ 到 $a_{i,n}$ 构成一个 $1$ 到 $n$ 的排列。

另外，每个人都有若干个下家，每次传递炸弹只能向自己的下家中的一个传递。（保证下家中没有自己，不能不传）

炸弹初始在编号为 $1$ 的玩家的手中，并且有一个参数 $t$ ，表示炸弹将在传递 $t$ 次后爆炸。

每个玩家都想使他的仇恨值尽量大的人在最后炸弹爆炸时收到炸弹。

假设所有玩家都是绝顶聪明的，请问谁将在最后收到炸弹？

输入格式

第一行输入两个整数 $n,t$ ，表示人数和炸弹参数。

接下来 $n$ 行每行 $n$ 个数 ，其中第 $i$ 行第 $j$ 列的数表示 $a_{i,j}$ 。

接下来 $n$ 行，第 $i$ 行开头一个整数 $m_i$ ，表示 $i$ 的下家个数。紧接着 $m_i$ 个互不相同且不等于 $i$ 的整数表示 $i$ 的所有下家。

输出格式

一个整数，表示最后收到炸弹的人。

输入输出样例

输入#1

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

输出#1

3

说明/提示

【样例 #1 解释】

首先，炸弹将在两次传递后爆炸。

如果 $1$ 号第一次传递给 $2$ 号，那么 $2$ 号再传递给 $3$ 号后炸弹爆炸。

如果 $1$ 号第一次传递给 $4$ 号，那么 $4$ 号再传递给 $2$ 号后炸弹爆炸。

由于 $1$ 号对 $3$ 号的仇恨值更大，因此他会首先传给 $2$ 号，并使得最终炸弹落到 $3$ 号手上。

注意，虽然假如首先传递给 $3$ 号后会再到 $4$ 号手上，但由于 $3$ 不是 $1$ 的下家，所以这是不合法的。

数据范围

对于 $20\%$ 的数据，满足 $n=2$ 。

对于另外 $40\%$ 的数据，满足 $n\leq 5,t\leq 5$ 。

对于 $100\%$ 的数据，满足 $n\le 1000,\sum_{i=1}^n m_i\le 5000,1\le t\le 5000,m_i\ge 1$ 。