B - Binary Alchemy Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

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

Score : 200 points

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