Problem J: J's Final Problem

Problem

不思議なダンジョンとは構造の変化を伴うダンジョンである。不思議なダンジョンは階層が深いものから浅いものまで様々なものがあり、深い階層には凶悪なモンスターが生息していたり、財宝が眠っていたりする。ジェイは不思議なダンジョンを研究している研究者である。ある日、新しいダンジョンを掘っていたところ、とても大きく深いダンジョンに繋がってしまった。ジェイはこのダンジョンを「ジェイの最終問題」と名付けた。このダンジョンの調査が、優秀な冒険者であるあなたに依頼されることになった。冒険者の目的はできるだけ深い層のフロアに到達することである。このダンジョンの特徴を以下に述べる。

• 地上からダンジョンの地下1階の部屋への下りの階段は1つしか存在しない。
• 各部屋は1つの上りの階段と2つの下りの階段が存在する。
• 2つの下りの階段のうち片方を右の階段、もう片方を左の階段とする。
• 冒険者が階段を降りた際に、ダンジョンの構造が変化することがある。
• 階段を降りるとは、地下i階のある部屋から地下i+1階のある部屋へ降りることを示す。
• 階段を上った場合はダンジョンに対して何も変化を及ぼさない。
• 地下n階目には階段は存在しない。

最近、ジェイの最終問題に関する石碑が発見された。 どうやら、各階の階段を降りたときの変化がメモとして記されているようだ。 メモの形式は、

num1 direction1 : num2 direction2

という形である。 地下num1階のすべての部屋について、direction1の階段を降りている途中で、地下num2階のすべての部屋について、 direction2の階段を降りた先の部屋が消滅し、さらにそこから階段を降りることによって到達できる部屋や階段がすべて消滅する。部屋や階段の消滅に冒険者が巻き込まれた場合、冒険は失敗する。地下i階から地下i+1階へ向かう階段の途中で冒険者が失敗した場合は地下i階まで到達したものとして扱う。 石碑において言及されていない階段は、その階段を降りてもダンジョンの構造に変化を及ぼさないことを示す。

冒険者はこの石碑をヒントにして探索を行うことにした。

ダンジョンの深さnとメモの情報がm個与えられるので、最大地下何階まで到達できるかを答えなさい。

Input

入力は複数のデータセットからなる。

n　m
memo1
memo2
…
memom

最初にn,mが与えられる。 それぞれ、ダンジョンの変化前の最下層の階数、石碑のメモの数を表す。 次にm行にわたりメモの情報 num1 direction1 : num2 direction2 が与えられる。

Constraints

入力は以下の条件を満たす。

• 入力に含まれる値はすべて整数
• 1 ≤ n ≤ 10000
• 0 ≤ m ≤ (n-1)×4
• 1 ≤ num1,num2 ≤ n-1
• direction1,direction2は"left"と"right"のいずれかである。

Output

最大地下何階まで降りることができるか1行に出力して答えよ。

Sample Input1

10 2
9 left : 9 left
9 right : 9 right

Sample Output1

9

Sample Input2

4 5
1 left : 2 right
2 left : 3 right
2 left : 3 left
1 right : 3 left
2 right : 3 right

Sample Output2

3