Định tuyến

Toàn bộ hệ thống máy chủ của công ty X có thể được biểu diễn dưới dạng một đồ thị có hướng. Có n máy chủ được đánh số từ 1 đến n. Máy chủ A có thể đi tới máy chủ B nếu có một tuyến đường có hướng $A \rightarrow B$, nhưng để đi từ máy chủ B tới máy chủ A, cần phải tồn tại tuyến đường theo chiều ngược lại $B \rightarrow A$. Mỗi máy chủ được biểu diễn như một đỉnh, và mỗi tuyến đường được biểu diễn như một cạnh trong đồ thị có hướng.

Bảng định tuyến được mô tả bởi hai mảng: $nodes\_from$ và $nodes\_to$. Tuyến đường thứ $i$ bắt đầu từ máy chủ $nodes\_from[i]$ và kết thúc tại máy chủ $nodes\_to[i]$.

Máy chủ trung tâm được đánh số là s.

Yêu cầu: Người quản lý muốn thiết lập thêm một số tuyến đường mới để từ máy chủ trung tâm có thể đi tới tất cả các máy chủ trong mạng. Hãy tìm số lượng tuyến đường có hướng mới tối thiểu cần thiết lập để máy chủ trung tâm có thể đi tới mọi máy chủ trong mạng.

Trong trường hợp không cần thiết lập thêm tuyến đường nào, kết quả là 0.

Đầu vào: Dòng đầu tiên của đầu vào chứa hai số nguyên $nodes$ $(2 \leq nodes \leq 10^5)$ và $routes$ $(1 \leq routes \leq \min(2 \cdot 10^5, nodes \cdot (nodes- 1)))$ — số lượng máy chủ và số lượng tuyến đường trong mạng.

Trong $routes$ dòng tiếp theo, dòng thứ $i$ $(0 \leq i < routes)$ chứa hai số nguyên $nodes\_from[i]$ và $nodes\_to[i]$ mô tả một tuyến đường có hướng trong mạng.

Dòng cuối cùng của đầu vào chứa một số nguyên s $(1 \leq s \leq nodes)$ — chỉ số của máy chủ trung tâm.

Đầu ra: In ra số lượng tuyến đường tối thiểu cần thiết lập để máy chủ trung tâm có thể đi tới tất cả các máy chủ trong mạng.

Giải thích: Ví dụ 1:

• $nodes = 6$
• $routes = 2$
• $nodes\_from = [4, 5]$, $nodes\_to = [1, 2]$
• $s = 6$

Có 6 máy chủ và hiện có 2 tuyến đường có hướng đã được thiết lập. Tuyến thứ nhất bắt đầu từ máy chủ 4 và kết thúc tại máy chủ 1. Tuyến thứ hai bắt đầu từ máy chủ 5 và kết thúc tại máy chủ 2.

Máy chủ 6 là máy chủ trung tâm, mạng lưới máy chủ có thể được biểu diễn như trong đồ thị bên dưới:

Để máy chủ trung tâm có thể đi tới tất cả các máy chủ trong mạng, một cách thiết lập số tuyến đường tối thiểu là:

• Bắt đầu từ máy chủ 6 và kết thúc tại máy chủ 3
• Bắt đầu từ máy chủ 3 và kết thúc tại máy chủ 5
• Bắt đầu từ máy chủ 5 và kết thúc tại máy chủ 4

Sau khi thiết lập 3 tuyến đường có hướng mới, máy chủ trung tâm có thể đi tới tất cả các máy chủ trong mạng và đây là số tuyến đường ít nhất cần thêm. Do đó, đáp án là 3.

Ví dụ 2:

• $nodes = 4$
• $routes = 3$
• $nodes\_from = [1, 2, 2]$, $nodes\_to = [2, 3, 4]$
• $s = 1$

Có 4 máy chủ và 3 tuyến đường đã được thiết lập sẵn:

• $1 \rightarrow 2$
• $2 \rightarrow 3$
• $2 \rightarrow 4$

Trong trường hợp này, máy chủ trung tâm đã có thể đi tới tất cả các máy chủ trong mạng. Do đó, đáp án là 0.

Ví dụ 3:

• $nodes = 6$
• $routes = 7$
• $nodes\_from = [4, 3, 6, 1, 2, 1, 5]$, $nodes\_to = [3, 1, 5, 2, 3, 3, 6]$
• $s = 2$

Mạng lưới ban đầu:

Sau khi thiết lập thêm 2 tuyến đường mới:

Do đó, đáp án là 2.

Ví dụ 1:

Đầu vào:

6 2
4 1
5 2
6

Đầu ra:

3

Ví dụ 2:

Đầu vào:

4 3
1 2
2 3
2 4
1

Đầu ra:

0

Ví dụ 3:

Đầu vào:

6 7
4 3
3 1
6 5
1 2
2 3
1 3
5 6
2

Đầu ra:

2