Baltic Olympiad in Informatics 2018 - day 1

Start

2018-04-27 23:00 AKDT

Baltic Olympiad in Informatics 2018 - day 1

End

2018-04-28 04:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -952 days 17:42:26

Time elapsed

5:00:00

Time remaining

0:00:00

Problem A
愛の多角形

誰もが知っているように、多くの登場人物が登場するテレビの昼メロは、深刻な複雑な恋愛ドラマにつながることがあります。 あるテレビ番組では、$N$人の登場人物がいます。各登場人物は、$1$人の登場人物(自分自身かもしれません)を愛しています。 以降、$2$人の登場人物がお互いを愛している場合に、彼らは恋愛関係にあると呼びます。

より複雑な状況として、“愛の多角形”と呼ばれるものがあります。 最初の登場人物が2番目の登場人物を愛し、2番目の登場人物が3番目の登場人物を愛し、最後の登場人物が1番目の登場人物を愛しているというように、 3人以上の登場人物が環状に愛している状況を“愛の多角形”になっていると呼びます。

最新の調査によると、視聴者はこのドラマに飽き飽きして、もっとロマンチックなものがいいと思っているようです。 そのため、全員が恋愛関係にあるように、登場人物の誰かを愛の矢で撃つことにしました。 愛の矢で撃つことで、その登場人物の愛する人を(任意の登場人物に)変えることができます。

全員が恋愛関係にあるようになるために必要な愛の矢の最小本数はいくつでしょうか?

入力

入力の最初の行には、登場人物の人数を表す整数$N$が含まれています。 続く$N$行はすべてスペースで区切られた2つの名前$s$$t$を含んでいます。 $s$という名前の登場人物は、最初は$t$という名前の登場人物を愛しています。 登場人物の名前は、$10$文字以下の英小文字で構成されています。

出力

1つの整数で、全員を恋愛関係にさせるために必要な愛の矢の最小本数を出力してください。 不可能な場合は、-1を出力します。

制約

あなたのソリューションは、テストグループのセットでテストされ、それぞれのグループにポイントが定義されています。 各テストグループにはテストケースのセットが含まれています。 テストグループのポイントを得るためには、テストグループ内のすべてのテストケースが成功する必要があります。 あなたの最終的なスコアは、1回の提出での最大スコアとなります。

グループ

ポイント

制限

追加の制約

1

21

$2 \le N \le 20$

 

2

25

$2 \le N \le 100\, 000$

Each character is loved by someone (possibly themselves).

3

29

$2 \le N \le 100\, 000$

There are no relationships or “love polygons”.

4

25

$2 \le N \le 100\, 000$

 

サンプルの説明

\includegraphics[width=0.5\textwidth ]{polygonfig.pdf}

最初の例は上の図のようになります。上段は初期の恋愛状況を示しており、$s$から$t$に向けられた矢印は、$s$が初期に$t$を愛していることを示しています。ピンク色は、唯一の最適解で愛の矢を撃つ必要がある3人の登場人物を強調しています。下段はその後の状況を示しています。

2つ目の例(group 3の制約条件を満たす)では、最適解がいくつかあります。 その一つは、a, b, dに愛の矢を撃ち、b, a, cに恋をさせることです。

3つ目の例では愛の三角形ができており、誰に愛の矢を撃っても、必ず誰かが残ってしまいます。