078 - Easy Graph Problem(★2)
解説
/
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点:2 点
問題文
N 頂点 M 辺の連結な単純無向グラフが与えられます。グラフの頂点には、それぞれ 1 から N までの番号が振られています。 i 番目の辺は、頂点 a_i と b_i を双方向に結んでいます。
以下の条件を満たす頂点の個数はいくつあるか出力してください。
- 自分自身より頂点番号が小さい隣接頂点がちょうど 1 つ存在する
制約
- 2 \leq N \leq 100000
- N - 1 \leq M \leq \mathrm{min}(\frac{N(N - 1)}{2}, 100000)
- 1 \leq a_i, b_i \leq N
- 与えられるグラフは単純グラフである
- 与えられるグラフは連結である
- 入力はすべて整数で与えられる
入力
入力は以下の形式で標準入力から与えられます。
N M a_1 b_1 \vdots a_{M} b_{M}
出力
条件を満たす頂点の個数を一行に出力してください。
入力例 1
5 5 1 2 1 3 3 2 5 2 4 2
出力例 1
3
条件を満たす頂点は、2, 4, 5 の 3 つです。
- 頂点 2 は、自分自身より頂点番号が小さい隣接頂点として、頂点 1 のみをもつ
- 頂点 4 は、自分自身より頂点番号が小さい隣接頂点として、頂点 2 のみをもつ
- 頂点 5 は、自分自身より頂点番号が小さい隣接頂点として、頂点 2 のみをもつ
入力例 2
2 1 1 2
出力例 2
1
条件を満たす頂点は 2 のみです。
入力例 3
7 18 7 2 1 6 5 2 1 3 7 6 5 3 5 6 5 4 1 7 2 6 3 4 5 1 4 7 4 6 5 7 3 2 4 2 1 4
出力例 3
0