STNODE - VOI09 Nút st - xung yếu

Giới hạn

• Thời gian: 0.2s
• Bộ nhớ: 1536MB
• Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

 

Bản đồ giao thông của hành tinh X bao gồm n thành phố được đánh số từ 1 đến n và m đoạn đường một chiều nối các cặp thành phố, giữa hai thành phố bất kỳ có không quá một đoạn đường cùng chiều nối chúng. Thành phố s là thủ đô của hành tinh, từ đó có thể di chuyển theo các đoạn đường nối giữa các thành phố để đến bất cứ thành phố nào trong số các thành phố còn lại. Thành phố t là một điểm du lịch ưa thích của người dân thủ đô. Hàng năm có một lượng lớn người dân thủ đô đến nghỉ ngơi tại điểm du lịch hấp dẫn này. Vì thế, trong các mùa du lịch ách tắc giao thông trên đường đi từ s đến t thường xuyên xảy ra tại một số nút giao thông. Do đó, Bộ Giao thông của hành tinh X muốn xác định các nút giao thông này. Ta nói thành phố a ( a ≠ s và a ≠ t) là nút st-xung yếu nếu mọi đường đi từ s đến t đều phải đi qua a.

Yêu cầu: Hãy xác định số lượng các nút st-xung yếu .

Dữ liệu:

• Dòng đầu tiên chứa 4 số nguyên dương n, m, s, t (3 ≤ n ≤ 10 ⁴ , m ≤ 10 ⁵ );
• m dòng tiếp theo mô tả sơ đồ giao thông trên hành tinh X: Dòng thứ i chứa hai số nguyên u _i , v _i cho biết có đoạn đường một chiều đi từ thành phố u _i đến thành phố _i , i = 1, 2, ..., m. Các số liên tiếp trên cùng dòng được ghi cách nhau bởi ít nhất một dấu cách.

Kết quả

• Một số nguyên duy nhất là số lượng nút st-xung yếu .

Ví dụ

Dữ liệuKết quả


7 10 1 5
1 2
1 3
2 4
3 4
4 5
5 6
6 2
6 7
7 3
7 51

Ràng buộc: 60% số tests ứng với 60% số điểm của bài có 3 ≤ n ≤ 100.

---

• Người up: beo_map
• Nguồn bài: Thi HSG Quốc gia 2009