1406 - 友達の友達は友達？

時間制限 1 秒 / メモリ制限 64 MB / 得点 1 / Writer r1910 / x 7 / 統計 /

TLE
1sec
MLE
64MB
得点
1

問題

世界地図において極東に位置する$R$帝国は、近年重大な社会問題を抱えていた。
それは、「友達の友達」は友達であるかというものである。
この国では友好関係が非常に重視される。 それ故「友達の友達の友達の・・・」となると、友達であるかどうかも分からないのだ。
そこで現帝王であるキング山本は、友達の定義を以下のようにした。

  • 「友達」が現れた回数が$C$回以下のとき、友達とする。

例えば、$C=2$の場合、「友達」が現れた回数が二回以下の場合、友達となる。つまり、「友達」と「友達の友達」のみが友達として認められる。
$R$帝国の役人であるあなたは、 $N$人の交友関係からそれぞれの友達の人数を算出することになった。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $C$
$a_1$ $b_1$ 
$a_2$ $b_2$
$\vdots$
$a_M$ $b_M$

1行目に調べる人数$N$、交友関係の数$M$、「友達」の回数$C$が与えられる。
続く$M$行に$a_i$と$b_i$が「友達」であることが示される。

出力

1~N人目の友達の人数を改行区切りで出力すること。 出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

  • $2 \leq N \leq 1000$
  • $1 \leq M \leq 1000$
    • 。
  • $1 \leq C \leq 999$
  • $1 \leq a_i,b_i \leq N$

入出力例

入力例1

3 2 1
1 2
2 3

出力例1

1
2
1

今回は「友達」が一回以下の場合友達になります。 1と3は「友達の友達」なので友達ではありません。

入力例2

3 3 2
1 2
2 3
3 1

出力例2

2
2
2

$N$人全てが友達になります。幸せですね。


解説（クリックで開く）

この問題は、「友達」の回数である$C$が重要です。問題文に友達という単語があるため一見$UnionFind$に見えますが、$UnionFind$はグループ分けをするデータ構造のため、使用することができません。ではどうするのかというと、「友達」の回数を「人と人との距離」と考え、$BFS$や$DFS$を行い、各人同士の距離が$C$以下の場合を数えます。$BFS$が想定解です。(そっちの方が楽だと思います。)