#1087. NET - Đường truyền quan trọng

Cho một mạng gồm tập hợp các nút và tập các đường truyền hai chiều nối giữa các cặp nút. Người ta biết rằng mạng này thông suốt, tức là mọi cặp nút trong mạng đều có thể truyền tin cho nhau. Một số nút trong mạng cung cấp dịch vụ còn một số nút khác cung cấp dịch vụ cho tất cả các nút (kể cả nó). Có thể có một nút cung cấp cả hai dịch vụ. Nếu một đường truyền trực tiếp bị hỏng có thể làm cho một số nút trong mạng không thể sử dụng một trong hai dịch vụ. Các đường truyền như vậy được gọi là các đường truyền quan trọng. Bạn hãy viết chương trình xác định số đường truyền quan trọng trong mạng.

Dữ liệu vào:

• Dòng đầu tiên ghi số và . Trong đó là số nút trong mạng, là số đường truyền trực tiếp trong mạng, là số nút cung cấp dịch vụ và là số nút cung cấp dịch vụ . Các nút được đánh số từ đến
• Dòng thứ hai ghi số là số hiệu các nút cung cấp dịch vụ
• Dòng thứ ba ghi số là số hiệu các nút cung cấp dịch vụ
• Mỗi dòng trong số dòng tiếp theo ghi hai số thể hiện một đường truyền trực tiếp nối nút và nút

Dữ liệu ra:

• Một số nguyên thể hiện số lượng đường truyền quan trọng trong mạng

Ví dụ:

Dữ liệu vào:

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

Dữ liệu ra:

3

Giải thích:

• Các đường truyền quan trọng là: