Thủ đô

Nước \(X\) là một đất nước rất xinh đẹp và giàu có. Ở đây có \(n\) thành phố, và một trong \(n\) thành phố đó chính là thủ đô của đất nước. Nước \(X\) đã có sẵn \(m\) con đường nối một chiều nối các thành phố. Tuy nhiên chính phủ nhận thấy rằng từ thủ đô, ta có thể không đến được một số thành phố. Vì vậy chính phủ quyết định xây thêm một số các con đường một chiều, sao cho sau khi xây xong, từ thủ đô có thể đến tất cả \(n - 1\) thành phố còn lại và số con đường xây thêm phải là ít nhất.

Với nhân lực hiện tại của chính phủ, họ chỉ có thể tính thủ công số con đường, vì vậy nếu số thành phố cực lớn thì họ không thể tính trong \(1\)s được. Vậy nên, các coder của đất nước, hãy viết chương trình tính toán số lượng con đường ít nhất cần phải xây.

Input

Dòng đầu tiên gồm \(3\) số nguyên dương \(n, m, s\) - số lượng thành phố, số con đường đã có, thủ đô của đất nước.

\(m\) dòng tiếp theo, mỗi dòng mô tả một con đường một chiều.

Output

Kết quả bài toán

Example

9 9 1
1 2
1 3
2 3
1 5
5 6
6 1
1 8
9 8
7 1

3

Scoring

\(30\%\) số test có \(n <= 20, m <= 30\).

\(30\%\) số test có \(n, m <= 5000\).

\(40\%\) số test còn lại \(n, m <= 2.10^5\).