K - Say!Yes!Kyosan Beam
Assam
2
s
1024
MB
200
点
問題文
寺子さんは天文台から京都市内に向けて京産ビームを放つことにしました。ビームは一方向にしか進みません。京都市内には京産ビームの増幅装置が$N$個あり、各増幅装置には$1$から$N$までの数字が割り振られています。増幅装置は0個以上の別の増幅装置に京産ビームを放っています。最初、寺子さんは1番目の増幅装置にのみ京産ビームを放っており、ビームの本数は$M＋1$本です。$i=1,2,…,M$ に対し、$i$番目のビームは増幅装置$a_i$から増幅装置$b_i$にビームを放っています。
ある増幅装置から、別の増幅装置に京産ビームを放ち、最終的に元の増幅装置に京産ビームが放たれることを、京産サイクルと定義します。この京産サイクルが発生すると、増幅装置が互いに増幅し合い、京産サイクル上の増幅装置が全て爆発してしまいます。
京産サイクルが発生するなら爆発した増幅装置の個数の合計を、発生しないなら$Happy$を出力してください。
制約
- $1 \leq N \leq 10^4$
- $1 \leq a_i \leq N$
- $ 1 \leq b_i \leq N$
- $ a_i \neq b_i $
- $ 0 \leq M \leq 2\times10^4 $
- 入力は全て整数
入力
1行目に京産ビームの増幅装置の数を表す $N$ と、ビームの本数を表す $M$ が空白区切りで与えられます。
増幅装置 $a_i$ から増幅装置 $b_i$ にビームが放たれていることを表す $a_i, b_i$ が空白区切りで $M$ 行与えられます。
$N$ $M$
$a_1$ $b_1$
.
.
.
$a_M$ $b_M$
出力
爆発した増幅装置の個数の合計もしくは$Happy$を1行で出力してください。
入力例 1
4 4
1 2
2 3
3 4
4 2
入力例 2
6 8
1 2
2 3
3 4
4 2
1 5
5 6
6 3
4 5
出力例 2
5
- Example2説明画像
$2 \to 3 \to 4 \to 2$と$5 \to 6 \to 3 \to 4 \to 5$の2つの京産サイクルが発生しているように見えますが、$3 \to 4$の部分で共有しているので、{$2, 3, 4, 5, 6$}の増幅装置を含む1つの京産サイクルとみなします。よって5を出力します。
入力例 3
4 3
1 2
1 3
2 4