#544. CUTBRIDGES – Khớp và cầu

Xét đơn đồ thị vô hướng có đỉnh và cạnh. Người ta định nghĩa một đỉnh gọi là khớp nếu như xoá đỉnh đó và tất cả các cạnh liên thuộc với nó sẽ làm tăng số thành phần liên thông của đồ thị. Tương tự như vậy, một cạnh được gọi là cầu nếu xoá cạnh đó sẽ làm tăng số thành phần liên thông của đồ thị.

Bài toán: Cho đơn đồ thị vô hướng , hãy liệt kê các khớp và cầu của đồ thị.

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên và là số đỉnh và số cạnh của ;
• dòng tiếp theo, mỗi dòng chứa một cặp số cho biết một cạnh nối hai đỉnh và trong .

Dữ liệu ra:

• Dòng đầu ghi hai số nguyên và là số khớp và số cầu của đồ thị;
• Dòng thứ hai (nếu ) ghi số nguyên dương là chỉ số các đỉnh khớp;
• dòng tiếp theo, mỗi dòng ghi một cặp số nguyên là hai đỉnh liên thuộc một cầu.

Ví dụ:

Dữ liệu vào:

10 12
1 10
10 2
10 3
2 4
4 5
5 2
3 6
6 7
7 3
7 8
8 9
9 7

Dữ liệu ra:

4 3
2 3 7 10
1 10
2 10
3 10

Giới hạn:

• .