Một đồ thị có hướng được gọi là bán liên thông (Semi-Connected) nếu thỏa mãn: , tồn tại đường đi từ đến hoặc từ đến . Tức là với bất kỳ hai điểm nào trong đồ thị, luôn có một đường đi có hướng từ đến hoặc từ đến .
Nếu thỏa mãn là tập hợp tất cả các cạnh trong có hai đầu mút thuộc , thì được gọi là một đồ thị con cảm sinh (induced subgraph) của . Nếu là đồ thị con cảm sinh của và bán liên thông, thì được gọi là đồ thị con bán liên thông của . Nếu là đồ thị con bán liên thông có chứa số lượng đỉnh nhiều nhất trong tất cả các đồ thị con bán liên thông của , thì là đồ thị con bán liên thông lớn nhất của .
Cho một đồ thị có hướng , hãy tìm số lượng đỉnh của đồ thị con bán liên thông lớn nhất của , và số lượng các đồ thị con bán liên thông lớn nhất khác nhau . Vì có thể rất lớn, chỉ cần xuất số dư của khi chia cho .
Dữ liệu:
Dòng đầu tiên chứa ba số nguyên . lần lượt là số đỉnh và số cạnh của đồ thị , có ý nghĩa như đã mô tả.
dòng tiếp theo, mỗi dòng chứa hai số nguyên dương , biểu thị một cạnh có hướng .
Các điểm trong đồ thị được đánh số . Đảm bảo không có cạnh nào xuất hiện hai lần.
