Biến đổi số
View as PDFCho ~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
This comment is hidden due to too much negative feedback. Show it anyway.