17738번 - Voltage 서브태스크다국어

あなたは Just Odd Inventions 社を知っているだろうか？この会社の業務は「ただ奇妙な発明 (just odd inventions)」をすることである．ここでは略して JOI 社と呼ぶ．

JOI 社のとある実験室には，複雑な電気回路がある．回路は N 個の節点と M 本の細長い電気抵抗からな る．節点には 1 から N までの番号が付けられている．各節点は「高電圧」または「低電圧」のいずれかの 状態に設定することができる．各電気抵抗は 2 個の節点を結んでおり，それらの節点の一方が「高電圧」， もう一方が「低電圧」の状態にあるときに電流が流れる．「高電圧」の節点どうし，あるいは「低電圧」の 節点どうしを結んでいる電気抵抗には，電流は流れない．

ある日，JOI 社はこの回路のメンテナンスのため，1 本の電気抵抗を選んで，その電気抵抗にのみ電流が 流れず，残りの M − 1 本には電流が流れるように，各節点の電圧を設定することになった．この条件を満 たすために，電流を流さない電気抵抗として選べるものは何本あるだろうか？

なお，JOI 社がこの奇妙な回路を用いてどのような発明をしているかは，社内でも最高機密であり社長 以外の誰も知らない．

回路の情報が与えられたとき，メンテナンスの際に電流を流さない電気抵抗として選ぶことができる電 気抵抗の本数を求めるプログラムを作成せよ．

標準入力から以下のデータを読み込め．

• 1 行目には，整数 N, M が空白を区切りとして書かれており，節点が N 個，電気抵抗が M 本あるこ とを表す．
• 続く M 行のうちの i 行目 (1 ≤ i ≤ M) には，整数 A_i, B_i (1 ≤ A_i ≤ N, 1 ≤ B_i ≤ N, A_i ≠ B_i) が空白を区 切りとして書かれており，i 番目の電気抵抗が節点 A_i と節点 B_i を結んでいることを表す

標準出力に，メンテナンスの際に電流を流さない電気抵抗として選ぶことができる電気抵抗の本数を 1 行で出力せよ．

• 2 ≤ N ≤ 100 000．
• 1 ≤ M ≤ 200 000．

• N ≤ 1 000．
• M ≤ 2 000．

• どの節点からどの節点へも，結ばれている電気抵抗を何本か辿って到達できる．
• M = N を満たす．

• どの節点からどの節点へも，結ばれている電気抵抗を何本か辿って到達できる．
• M ≤ N + 100 を満たす．

追加の制限はない．