Cho \(m\) máy biến đổi số được đánh số từ 1 tới \(m\) và một 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 \leq a_{i},\ b_{i} \leq n)\), máy nhận đầu vào là số nguyên dương \(a_{i}\) và cho đầu ra là số nguyên dương \(b_{i}\).

Ta nói số nguyên dương \(x\) có thể biến đổi thành số nguyên dương \(y\) nếu \(x\ = \ y\) hoặc tồn tại một dãy hữu hạn các số nguyên dương \(x = p_{1},\ p_{2},\ \ldots\ ,p_{k}\ = y\) sao cho đối với hai phần tử liên tiếp \(p_{i},\ p_{i + 1}\) bất kỳ trong dãy, luôn tìm được một trong số các máy đã cho có đầu vào là \(p_{i}\) và đầu ra là \(p_{i + 1}\).

Yêu cầu: Cho trước số nguyên dương \(t\ (t\ \leq n)\), hãy bổ sung thêm một số ít nhất máy biến đổi số để bất kỳ số nguyên dương nào từ 1 tới \(n\) đều có thể biến đổi thành \(t\).

Dữ liệu vào:

+ Dòng đầu ghi \(n,\ m,\ t\ (1 \leq n,m,t \leq 10000)\ \);

+ \(m\) dòng tiếp theo, mỗi dòng chứa một cặp số tương ứng với một máy biến đổi số.

Kết quả:

+ Ghi một số duy nhất là số lượng máy cần bổ sung, nếu không cần bổ sung thêm máy nào thì ghi số 0

Ví dụ:

Ràng buộc:

• 50% số test có \(1 \leq n,m,t \leq 100\)

• 50% số test không có ràng buộc thêm