103701: [Atcoder]ABC370 B - Binary Alchemy

Problem Statement

There are $N$ types of elements numbered $1, 2, \ldots, N$.

Elements can be combined with each other. When elements $i$ and $j$ are combined, they transform into element $A_{i, j}$ if $i \geq j$, and into element $A_{j, i}$ if $i < j$.

Starting with element $1$, combine it with elements $1, 2, \ldots, N$ in this order. Find the final element obtained.

Constraints

• $1 \leq N \leq 100$
• $1 \leq A_{i, j} \leq N$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$A_{1, 1}$
$A_{2, 1}$ $A_{2, 2}$
$\vdots$
$A_{N, 1}$ $A_{N, 2}$ $\ldots$ $A_{N, N}$

Output

Print the number representing the final element obtained.

Sample Input 1

4
3
2 4
3 1 2
2 1 2 4

Sample Output 1

2

• Combining element $1$ with element $1$ results in element $3$.

• Combining element $3$ with element $2$ results in element $1$.

• Combining element $1$ with element $3$ results in element $3$.

• Combining element $3$ with element $4$ results in element $2$.

Therefore, the value to be printed is $2$.

Sample Input 2

5
5
5 5
5 5 5
5 5 5 5
5 5 5 5 5

Sample Output 2

5

Sample Input 3

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

Sample Output 3

5

问题陈述

有$N$种元素，编号为$1, 2, \ldots, N$。

元素可以相互结合。当元素$i$和$j$结合时，如果$i \geq j$，它们会变成元素$A_{i, j}$；如果$i < j$，则会变成元素$A_{j, i}$。

从元素$1$开始，按此顺序将其与元素$1, 2, \ldots, N$结合。找出最终获得的元素。

约束条件

• $1 \leq N \leq 100$
• $1 \leq A_{i, j} \leq N$
• 所有输入值都是整数。

输入

输入从标准输入以下格式给出：

$N$
$A_{1, 1}$
$A_{2, 1}$ $A_{2, 2}$
$\vdots$
$A_{N, 1}$ $A_{N, 2}$ $\ldots$ $A_{N, N}$

输出

打印出获得的最终元素编号。

示例输入1

4
3
2 4
3 1 2
2 1 2 4

示例输出1

2

• 将元素$1$与元素$1$结合得到元素$3$。

• 将元素$3$与元素$2$结合得到元素$1$。

• 将元素$1$与元素$3$结合得到元素$3$。

• 将元素$3$与元素$4$结合得到元素$2$。

因此，要打印的值是$2$。

示例输入2

5
5
5 5
5 5 5
5 5 5 5
5 5 5 5 5

示例输出2

5

示例输入3

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

示例输出3

5