Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
Statistics

题目描述

有 $n$ 个人互相批评。

另提供矩阵 $A$。

规则如下:

  • 第一次,第 $1$ 个人批评第 $2$ 个人。

  • 如果第 $i-1$ 次为第 $u$ 个人批评第 $v$ 个人,

    那么第 $i$ 次为第 $v$ 个人批评第 $A_{v,u}$ 个人。

求第 $k$ 次是谁进行批评(注意:不是批评)。

输入格式

第一行:两个正整数,$n$ 和 $k$。

以下 $n$ 行:矩阵 $A$。矩阵的主对角线(就是从左上到右下的那条对角线)全是 $0$,其他部分由从 $1$ 到 $n$ 的正整数组成。

输出格式

一行:你的答案。

样例 #1

样例输入 #1

2 4
0 2
1 0

样例输出 #1

2

样例 #2

样例输入 #2

3 7
0 3 2
3 0 3
2 1 0

样例输出 #2

1

样例 #3

样例输入 #3

4 7
0 4 3 2
4 0 4 1
2 1 0 1
3 2 3 0

样例输出 #3

3

提示

数据范围

  • 对于 $35 pts$ 的数据,保证 $1\leq k\leq 10^5$。
  • 对于所有的数据,$2\leq n\leq 500$ 且 $1\leq k\leq 10^{18}$。