Problem B: あみだくじ
Problem Statement
会津合宿に参加予定の高槻さんは、家が貧乏であり、いつも紙をなるべく節約して使うようにしている。彼女は、会津合宿のチーム決めのために、他の参加者の人達とあみだくじをすることになった。
この合宿のあみだくじの作り方は次のようなものである。まず、紙にN本の縦棒を平行に書く。そして、M本の横棒を上から順番に、縦棒と垂直になるように、かつ横棒の高さが全て異なるように書いていく。例えば、Sample Input 1のあみだは、図1のようになる。
ここで、高槻さん、ちょっと不満げな表情。こんなに縦長にあみだくじを書いていると紙がもったいない。もっと、高さを圧縮できるはず。ということで、彼女のために以下に示すあみだくじの高さ圧縮の問題を解いてほしい。
まず、あみだくじの高さとは、同じ高さに存在する横棒をまとめて高さ1と数えて、これを一番下の横棒まで数えた値である。ここでは、高さ圧縮を行うために、各横棒を上下に自由に動かすことができるものとする。ただし、横棒を削除することも追加することも許されない。高さ圧縮をした後のあみだくじは、必ず以下の条件を満たしている必要がある。
- 横棒の端点が他の横棒の端点と接していない。
- 圧縮後のあみだくじを辿った結果と、圧縮前のあみだくじを辿った結果が一致している。
図2は、図1を圧縮したものである。「縦棒1と2を結ぶ横棒」が一番上まで移動して、「縦棒4と5を結ぶ横棒」と同じ高さとなり、この2つで高さ1。あとは、「縦棒3と4を結ぶ横棒」と「縦棒2と3を結ぶ横棒」は、それぞれ別の高さとなり、全体で高さ3である。
与えられたあみだくじを高さ圧縮し、圧縮後の高さを出力せよ。
Input
各データセットは、以下の形式で入力される。
N M a1 a2 ... aM
入力は全て整数である。Nは縦棒の数、Mは横棒の数を示す。続いて、M行にわたって横棒の情報が入力される。aiは、i番目の横棒が縦棒aiと、その1つ右の縦棒を結んでいることを表わしている。i番目の横棒は、i+1番目の横棒より上側に存在する。
Constraints
- 2 <= N <= 8
- 1 <= M <= 8
- 1 <= ai <= N - 1
Output
圧縮後のあみだくじの高さを1行で出力する。
Sample Input 1
5 4 4 3 1 2
Output for the Sample Input 1
3
Sample Input 2
4 3 1 2 3
Output for the Sample Input 2
3
高さ圧縮は行えないため、横棒の数Mを出力する。