User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

37.5% (6/16)

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

Sample Input 2

42 0

Sample Output 2

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

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

Submit

Status

Ranklist

121 . 勞贖 ᘛ⁐̤ᕐᐷ