Problem F
照明のスイッチ

アン・ブリット＝キャロラインは宝くじに当選しました。 彼女の新しい財産で、彼女はプライベートジェットと、いくつかの黒玉¹と、$N$個の部屋とそれらをつなぐ長い廊下で構成された巨大な家を購入しました。 それぞれの廊下は2つの部屋を結んでいますが、必ずしも特定の幾何学的なパターンに沿う必要はなく、どの2部屋を結んでもかまいません。 アンは環境保護に熱心なので、不必要に照明をつけないようにしています。 彼女は現在$1$番の部屋（唯一照明がついている部屋）に立っていますが、$N$番の部屋はもっと刺激的な場所になるかもしれないと考えています。

残念ながら、アン・ブリット＝キャロラインは暗闇を恐れています。 彼女は決して照明で照らされていない廊下を歩きたくありません。 幸いなことに、部屋から隣接する廊下に光が漏れることがあります。 それぞれの部屋について、アンはその部屋の照明が点灯しているときに、隣接するどの廊下に光が漏れるかを知っています。 ある部屋の照明は、その部屋の隣接する廊下を照らすほど強くはないが（廊下の光の角度が適切でない可能性があるため）、廊下の反対側の部屋の照明は強く照らされている可能性があります。 その場合は、一方の照明が点灯している場合のみ廊下を通行することができます。

アン・ブリット＝キャロラインは今、家の中の照明をつけたり消したりして回って、他の部屋の照明をつけずに$N$の部屋に行くことは可能なのかと考えています。 その場合、彼女はその過程で点灯する必要がある照明の最小数も知りたいと思っています。

入力

入力の1行目には、部屋の数を表す整数$N$ ($1\le N\le 500$)が入っています。

次の$N$行は、それぞれの部屋を表します。 $i$行目には、まず、数字の$s_i$ ($0\le s_i<N$)があり、次に、$s_i$個の整数$a_1、\dots ,a_s$ ($1\le a_j\le N,a_j\ne i$)が続きます。これらは、$i$番の部屋の照明で照らされる廊下の先にある部屋の番号を示します。

$M$を全ての$s_i$の和とすると、$0\le M\le 2000$を満たします。

出力

他のすべての部屋の照明が消された状態で部屋$N$に行くことができない場合は， “nej” を出力します。 そうでなければ、アン・ブリット＝キャロラインがそこに行くために必要な照明の数の最小値を整数で出力します。

採点

あなたのソリューションは、一連のテストケースグループでテストされます。 グループのポイントを得るためには、グループ内のすべてのテストケースが成功する必要があります。

サンプルの説明

最初の例では、アンのために考えられる戦略は、最初に部屋3に行ってその部屋の照明をつけることです。 その後、彼女は部屋1に行ってその部屋の照明を消し、（部屋3の照明が点灯している廊下を通って）部屋3に戻ることができます。 その後、彼女は部屋4に行き、その部屋の照明をつけ、部屋5（目的地）に行き、その照明をつけることができます。 その後、部屋4に戻ってその照明を消し、部屋3に行ってその照明を消し、最後に部屋3から部屋5に行くことができます。 合計で3つの照明をつけました（部屋3、4、5）。

2番目の例では、彼女は決して求める状態に到達することができません。部屋1の照明を消してしまうと、どこにも移動することができないからです。

5
2 2 3
1 4
2 4 1
1 5
1 3

3

4
1 2
2 3 4
1 2
1 3

nej

4
1 2
1 3
2 1 4
1 2

3