芸術家であるあなたは,作品の材料として多くのボールとそれらを結ぶための紐を用意した.ボールには順に番号を振っていくが,最初はボールのひとつを 1 番とするだけである.他のボールはまだ番号を振っていないし,どのボールも紐で結んでいない.
作品制作には以下の操作のどちらかを行うことを繰り返す.
最初はひとつのボールにしか番号がついていないので,まずは複製から始めることになる.
図 H-1 に Sample Input の 2 番目のデータセットの作品の制作過程を示す.
すべての真の芸術家と同様完璧主義者であるあなたは,不完全な作品には我慢できない.不満足な作品は,つないだ紐を全部引きちぎって一刻も早く完全に破壊してしまいたい.そこで,あなたは番号のついたボールのうちのいくつかを片手に,残り全てをもう一方の手に持って,ふたつの端点が左右の手にまたがるような紐を全部いっぺんに引きちぎることにした.この行為を 1 回だけ行うことでボールとボールを結ぶ紐を全て切断できれば,作品の破壊は成功である.逆に,同じ手に持ったボール同士を結ぶ紐があるようならば,それが切断されずに残ってしまうので,作品の破壊は失敗である.
図 H-2 は Sample Input の 2 番目のデータセットで作られる作品の破壊を試みる様子を示している.この作品を破壊するには,どちらの手にも 3 個以上のボールを持つ必要がある.
与えられた操作の列によって作られる作品について,上記のやり方でこれを破壊できるか判定せよ.できる場合は,少なくともいくつのボールを左手に持つ必要があるか求めよ.右手にはいくつのボールを持ってもよい.
入力は複数のデータセットからなる. 各データセットは次の形式で表される.
m
a1
⋮
am
m はあなたが行った操作の数を表す.m は正の整数であり,300 を超えない.
i 番目の操作 ai (i = 1, ..., m) は以下のいずれかの形式で与えられる.
COPY
COPY
操作の総数は 60 を超えないことが保証される.
LINK
u v入力の終わりは,ゼロだけからなる行で表される.入力に含まれるデータセットは 100 個以下である.
各データセットについて,ひとつの整数からなる行を出力する.上述の方法で作品を破壊することができるならば,そのとき左手に持つ必要があるボールの最小の個数を出力せよ.作品の破壊が不可能ならば −1 を出力せよ.
3 COPY LINK 1 2 COPY 8 COPY COPY LINK 1 2 LINK 1 3 LINK 1 3 COPY LINK 5 6 LINK 3 6 5 COPY LINK 1 2 COPY LINK 1 3 LINK 2 3 2 COPY COPY 0
2 3 -1 0