VOI 09 Bài 2 - Nút st - xung yếu

View as PDF

Submit solution


Points: 0.45 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Thi HSG Quốc gia 2009
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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 \neq s~ và ~a \neq t~) là nút st-xung yếu nếu mọi đường đi từ ~s~ đến ~t~ đều phải đi qua ~a~.

image

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

Input

  • Dòng đầu tiên chứa 4 số nguyên dương ~n, m, s, t~ ~(3 \leq n \leq 10^{4}, m \leq 10^{5})~;
  • ~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ố ~v_{i}~, ~i = 1, 2, \dots, 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.

Output

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

Giới hạn

60% số tests ứng với 60% số điểm của bài có ~3 \leq n \leq 100~.

Sample Input

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

Sample Output

1

Comments

Please read the guidelines before commenting.


There are no comments at the moment.