Biến đổi số

View as PDF

Submit solution


Points: 0.20 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho ~M~ máy biến đổi số được đánh số từ ~1~ đến ~M~ và ~1~ số nguyên dương ~N~. Hoạt động của máy ~i~ được xác định bởi cặp số nguyên dương (~a_i~, ~b_i~) ~(1 \le~ ~a_i~, ~b_i~ ~\le N)~. Máy nhận đầu vào là số nguyên dương ~a_i~ và trả lại ở đầu ra số nguyên dương ~b_i~.

Ta nói một số nguyên dương ~X~ có thể biến đổi thành số nguyên dương ~Y~ nếu hoặc ~X = Y~ hoặc tồn tại dãy hữu hạn các số nguyên dương ~X =~ ~P_1~, ~P_2~, ..., ~P_k~ ~= Y~ sao cho đối với ~2~ phần tử liên tiếp ~P_i~ và ~P_{i+1}~ bất kỳ trong dãy, luôn tìm được ~1~ trong số các máy đã cho để biến đổi ~P_i~ thành ~P_{i+1}~

Cho trước ~1~ số nguyên dương ~T~ ~(T \le N)~. Hãy bổ sung thêm ~1~ số ít nhất các máy biến đổi số để bất kì số nguyên dương nào từ ~1~ đến ~N~ đều có thể biến đổi thành ~T~

Input

  • Dòng ~1~: ~3~ số nguyên dương ~N~, ~M~, ~T~ ~(1 \le N~, ~M~, ~T \le 10^{4})~
  • ~M~ dòng tiếp theo mỗi dòng chứa ~1~ cặp số tương ứng với một máy biến đổi số. Các số trên một dòng cách nhau bởi ~1~ dấu cách

Output

Ghi ra ~1~ dòng duy nhất chứa ~1~ số nguyên dương là số lượng máy biến đổi số cần thêm

Sample Input

6 4 5
1 3
2 3
4 5
6 5

Sample Output

1

Comments

Please read the guidelines before commenting.



  • -6
    hung2007ng  commented on Jan. 24, 2024, 3:17 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.