Server Time:

User's AC Ratio in this contest

7.7% (1/13)

Submission's AC Ratio in this contest

2.4% (1/42)

Description

瑞米是隻聰明的老鼠,他知道餐廳裡有哪些地方有捕鼠器
餐廳裡共有 $N$ 個地點是必須常去的地方,他想製作一張地圖給他的家人

$N$ 個地點中任意兩個地點都有路可走,但是其中有 $m$ 條路有捕鼠器
他想盡可能的避開這些有捕鼠器的路,好規劃一個較安全的地圖

小林想要協助他製作地圖,正好他過去曾有寫程式的經歷(?)
地圖兩兩地點間至少要有一條路徑,該地圖最少可以容許幾個有捕鼠器的路?

(這裡路徑表示地點序列,使得一個地點與下個地點之間有路)

Input Format

第一列有兩個數 $N, m$ 分別為地點數以及有幾條捕鼠器的路 $(1 \le N \le 5\cdot 10^5, 0 \le m \le \min(5\cdot 10^5, \frac{N(N-1)}{2}))$
接著有 $m$ 列 $a_i, b_i$,表示地點 $a_i$ 與 $b_i$ 間的路中有捕鼠器 $(1 \le a_i, b_i \le N, a_i \not= b_i)$

Output Format

任兩地點間要有一條路徑的地圖最少能有幾個有捕鼠器的路

Sample Input 1

4 5
1 2
3 4
1 3
2 4
1 4

Sample Output 1

2

Sample Input 2

42 0

Sample Output 2

0

Sample Input 3

6 11
2 4
1 6
5 2
1 3
3 5
3 6
4 1
1 5
2 3
2 6
3 4

Sample Output 3

2

Hints

第一筆範測可由下圖表示:

其中一種最少捕鼠器路的地圖可用 $3$ 條路: $\{1, 2\}, \{4, 2\}, \{3, 2\}$ 所構成,且任意兩點存在一條路徑

Problem Source

CODEFORCES 1243D 0-1 MST

Subtasks

No. Testdata Range Score
1 0~45 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1
1 2000 524288 65536 1
2 2000 524288 65536 1
3 2000 524288 65536 1
4 2000 524288 65536 1
5 2000 524288 65536 1
6 2000 524288 65536 1
7 2000 524288 65536 1
8 2000 524288 65536 1
9 2000 524288 65536 1
10 2000 524288 65536 1
11 2000 524288 65536 1
12 2000 524288 65536 1
13 2000 524288 65536 1
14 2000 524288 65536 1
15 2000 524288 65536 1
16 2000 524288 65536 1
17 2000 524288 65536 1
18 2000 524288 65536 1
19 2000 524288 65536 1
20 2000 524288 65536 1
21 2000 524288 65536 1
22 2000 524288 65536 1
23 2000 524288 65536 1
24 2000 524288 65536 1
25 2000 524288 65536 1
26 2000 524288 65536 1
27 2000 524288 65536 1
28 2000 524288 65536 1
29 2000 524288 65536 1
30 2000 524288 65536 1
31 2000 524288 65536 1
32 2000 524288 65536 1
33 2000 524288 65536 1
34 2000 524288 65536 1
35 2000 524288 65536 1
36 2000 524288 65536 1
37 2000 524288 65536 1
38 2000 524288 65536 1
39 2000 524288 65536 1
40 2000 524288 65536 1
41 2000 524288 65536 1
42 2000 524288 65536 1
43 2000 524288 65536 1
44 2000 524288 65536 1
45 2000 524288 65536 1