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