Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NUMBER - Biến đổi số

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/number


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 (ai,bi) (1<=ai,bi<=N). Máy nhận đầu vào là số nguyên dương ai và trả lại ở đầu ra số nguyên dương bi.

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= P1,P2,...,Pk =Y sao cho đối với 2 phần tử liên tiếp Pi và Pi+1 bất kỳ trong dãy, luôn tìm được 1 trong số các máy đã cho để biến đổi Pi thành Pi+1

Cho trước 1 số nguyên dương T (T<=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<=N,M,T<=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

Example

Input:
6 4 5
1 3
2 3
4 5
6 5

Output:
1

Được gửi lên bởi:sieunhan
Ngày:2008-12-14
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET

hide comments
2021-05-27 18:02:46
Tham khảo: https://vnspoj.github.io/problems/NUMBER
2020-10-28 14:41:18
Code ac: https://ideone.com/yrJAJY
2020-06-10 04:18:55
vừa xem Trần Đức bo vừa code vẫn ac
2020-06-10 03:14:20
meo méo meo mèo meo
2020-06-10 03:13:28
Trần Đức Bo xin chào các Fan hâm mộ
2020-06-09 20:15:45
AhnTuan 10tin LHP ND bao bai nay de :))))
2019-07-13 17:53:24
AC: pornhub.com

Last edit: 2019-07-13 17:54:29
2019-07-11 22:28:26
Chung Ching Chong tuyên bố tụi mày tuổi tôm
2019-07-11 16:49:30
LHP NAM DINH 2 DAM AC
2019-07-11 08:08:20
AC chi la chuyen nho
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.