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\)

Dữ liệu vào

• Dòng đầu: \(3\) số nguyên dương \(N,M,T\) \((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

Dữ liệu ra

• 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

Input 1

6 4 5
1 3
2 3
4 5
6 5

Output 1

1