給一張$N$點$M$邊的無向圖,保證連通、不含有自環、重邊。
請輸出滿足$a < b$且原圖移除$a, b$兩點後會不連通的點對$(a, b)$數量。
第一行有兩個正整數$N, M(N\leq 2000, N - 1\leq M \leq \frac{N(N - 1)}{2})$,分別代表點數以及邊數。
接著$M$行每行有兩個正整數$u_i, v_i$,代表第$i$條邊連接$u_i$以及$v_i$。
子任務(測資) | 額外限制 | 分數 |
1 (0~31) | $N \leq 100$ | 21 |
2 (0~65) | $N \leq 800$ | 28 |
3 (0~99) | $N \leq 2000$ | 51 |
輸出一個整數代表有幾對$(a, b)$滿足$a < b$且移除點$a$以及點$b$後會造成圖不連通。
範例測資一:移除$(1, 3)$、$(1, 4)$、$ (2, 3)$、$ (2, 4)$、 $(3, 4)$、 $(3, 5)$、$ (3, 6)$、$ (4, 5)$、 $(4, 6)$後皆會造成圖不連通。
範例測資二:移除$(1, 3)$、$(2, 4)$後皆會造成圖不連通。
Problem Set by WeaK, waynetuinfor
No. | Testdata Range | Score |
---|---|---|
1 | 0~31 | 21 |
2 | 0~65 | 28 |
3 | 0~99 | 51 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 2000 | 262144 | 262144 | |
1 | 2000 | 262144 | 262144 | |
2 | 2000 | 262144 | 262144 | |
3 | 2000 | 262144 | 262144 | |
4 | 2000 | 262144 | 262144 | |
5 | 2000 | 262144 | 262144 | |
6 | 2000 | 262144 | 262144 | |
7 | 2000 | 262144 | 262144 | |
8 | 2000 | 262144 | 262144 | |
9 | 2000 | 262144 | 262144 | |
10 | 2000 | 262144 | 262144 | |
11 | 2000 | 262144 | 262144 | |
12 | 2000 | 262144 | 262144 | |
13 | 2000 | 262144 | 262144 | |
14 | 2000 | 262144 | 262144 | |
15 | 2000 | 262144 | 262144 | |
16 | 2000 | 262144 | 262144 | |
17 | 2000 | 262144 | 262144 | |
18 | 2000 | 262144 | 262144 | |
19 | 2000 | 262144 | 262144 | |
20 | 2000 | 262144 | 262144 | |
21 | 2000 | 262144 | 262144 | |
22 | 2000 | 262144 | 262144 | |
23 | 2000 | 262144 | 262144 | |
24 | 2000 | 262144 | 262144 | |
25 | 2000 | 262144 | 262144 | |
26 | 2000 | 262144 | 262144 | |
27 | 2000 | 262144 | 262144 | |
28 | 2000 | 262144 | 262144 | |
29 | 2000 | 262144 | 262144 | |
30 | 2000 | 262144 | 262144 | |
31 | 2000 | 262144 | 262144 | |
32 | 2000 | 262144 | 262144 | |
33 | 2000 | 262144 | 262144 | |
34 | 2000 | 262144 | 262144 | |
35 | 2000 | 262144 | 262144 | |
36 | 2000 | 262144 | 262144 | |
37 | 2000 | 262144 | 262144 | |
38 | 2000 | 262144 | 262144 | |
39 | 2000 | 262144 | 262144 | |
40 | 2000 | 262144 | 262144 | |
41 | 2000 | 262144 | 262144 | |
42 | 2000 | 262144 | 262144 | |
43 | 2000 | 262144 | 262144 | |
44 | 2000 | 262144 | 262144 | |
45 | 2000 | 262144 | 262144 | |
46 | 2000 | 262144 | 262144 | |
47 | 2000 | 262144 | 262144 | |
48 | 2000 | 262144 | 262144 | |
49 | 2000 | 262144 | 262144 | |
50 | 2000 | 262144 | 262144 | |
51 | 2000 | 262144 | 262144 | |
52 | 2000 | 262144 | 262144 | |
53 | 2000 | 262144 | 262144 | |
54 | 2000 | 262144 | 262144 | |
55 | 2000 | 262144 | 262144 | |
56 | 2000 | 262144 | 262144 | |
57 | 2000 | 262144 | 262144 | |
58 | 2000 | 262144 | 262144 | |
59 | 2000 | 262144 | 262144 | |
60 | 2000 | 262144 | 262144 | |
61 | 2000 | 262144 | 262144 | |
62 | 2000 | 262144 | 262144 | |
63 | 2000 | 262144 | 262144 | |
64 | 2000 | 262144 | 262144 | |
65 | 2000 | 262144 | 262144 | |
66 | 2000 | 262144 | 262144 | |
67 | 2000 | 262144 | 262144 | |
68 | 2000 | 262144 | 262144 | |
69 | 2000 | 262144 | 262144 | |
70 | 2000 | 262144 | 262144 | |
71 | 2000 | 262144 | 262144 | |
72 | 2000 | 262144 | 262144 | |
73 | 2000 | 262144 | 262144 | |
74 | 2000 | 262144 | 262144 | |
75 | 2000 | 262144 | 262144 | |
76 | 2000 | 262144 | 262144 | |
77 | 2000 | 262144 | 262144 | |
78 | 2000 | 262144 | 262144 | |
79 | 2000 | 262144 | 262144 | |
80 | 2000 | 262144 | 262144 | |
81 | 2000 | 262144 | 262144 | |
82 | 2000 | 262144 | 262144 | |
83 | 2000 | 262144 | 262144 | |
84 | 2000 | 262144 | 262144 | |
85 | 2000 | 262144 | 262144 | |
86 | 2000 | 262144 | 262144 | |
87 | 2000 | 262144 | 262144 | |
88 | 2000 | 262144 | 262144 | |
89 | 2000 | 262144 | 262144 | |
90 | 2000 | 262144 | 262144 | |
91 | 2000 | 262144 | 262144 | |
92 | 2000 | 262144 | 262144 | |
93 | 2000 | 262144 | 262144 | |
94 | 2000 | 262144 | 262144 | |
95 | 2000 | 262144 | 262144 | |
96 | 2000 | 262144 | 262144 | |
97 | 2000 | 262144 | 262144 | |
98 | 2000 | 262144 | 262144 | |
99 | 2000 | 262144 | 262144 |