0108 - Decorating The Pastures

USA Compution Olympiad 2014 US OPEN, BLONZE

Problem 3: Decorating The Pastures

原文 (English)

Farmer John has N (1 <= N <= 50,000) pastures, conveniently numbered 1...N, connected by M (1 <= M <= 100,000) bidirectional paths. Path i connects pasture A_i (1 <= A_i <= N) to pasture B_i (1 <= B_i <= N) with A_i != B_i. It is possible for two paths to connect between the same pair of pastures.

Bessie has decided to decorate the pastures for FJ's birthday. She wants to put a large sign in each pasture containing either the letter 'F' or 'J', but in order not to confuse FJ, she wants to be sure that two pastures are decorated by different letters if they are connected by a path.

The sign company insists on charging Bessie more money for an 'F' sign than a 'J' sign, so Bessie wants to maximize the number of 'J' signs that she uses. Please determine this number, or output -1 if there is no valid way to arrange the signs.

和訳 (Japanese)

Farmer John は N (1 ≦ N ≦ 50,000) 個の牧草地を所有し、それぞれの牧草地に 1 ... N の番号が付けられています。それぞれの牧草地は M (1 ≦ M ≦ 100,000) 本の双方向パスによって接続されています。i 番目のパスは、牧草地 A_i (1 ≦ A_i ≦ N) と牧草地 B_i (1 ≦ B_i ≦ N) で接続(A_i != B_i) されています。また、牧草地のペアが同じパスが存在することがあります。Bessie は Farmer John の誕生日のために牧草地を飾ることを決めました。彼女は、各農場に 'F' か 'J' どちらかの文字の大きな看板を置くことを望んでいますが、Farmer John を混乱させないために、彼女は それらの牧草地がパスで接続されている場合、2 つの牧草地が異なる文字で装飾されているようにしたいです。

看板会社は、'J' の看板より 'F' の看板の方がより多くのお金をチャージする必要があるようなので、Bessie は彼女が使用する 'J' の看板の数を最大化したいです。この数を表示してください。また配置する方法が存在しない場合、-1 を表示してください。

入力形式

N M
A1 B1
A2 B2
:
AM BM

1 行目に半角スペースで区切られた 牧草地の数 N と パスの本数 M が与えられる。
2 行目から M 行にかけて、A_iとB_iが与えられる。これは、A_iとB_iが双方向パスが存在することを表す。

出力形式

1行に、Bessie が設置できる 'J' の看板の数の最大値を整数で出力せよ。もし、設置する方法が存在しない場合は、-1 を出力せよ。

入出力例

入力例

4 4
1 2
2 3
3 4
4 1

出力例

2

解説

例えば、牧草地 1 と牧草地 3 に 'J'、牧草地 2 と牧草地 4 に 'F' を設置することで 'J' の看板の数の最大値となる。