题目描述
有 $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}$。