Một hệ thống gồm ~N~ máy chủ được kết nối bởi ~M~ kênh truyền dữ liệu hai chiều. Các máy chủ được đánh số từ ~1~ đến ~N~, mỗi kênh truyền nối trực tiếp hai máy chủ khác nhau.

Một gói tin được gửi từ máy chủ nguồn ~S~ đến một máy chủ ~v~ bằng cách đi qua một số kênh truyền. Do mọi kênh truyền đều có cùng độ trễ, hệ thống luôn lựa chọn một đường đi sử dụng ít kênh truyền nhất. Khi có nhiều đường đi như vậy, hệ thống có thể lựa chọn bất kỳ đường nào.

Để giám sát hệ thống, quản trị viên có thể đặt thiết bị theo dõi tại một máy chủ. Với mỗi máy chủ đích ~v~, máy chủ ~u~ được gọi là điểm giám sát của ~v~ nếu mọi đường đi ngắn nhất từ ~S~ đến ~v~ đều đi qua ~u~.

Hai đầu mút cũng được tính là nằm trên đường đi. Vì vậy, ~S~ và ~v~ luôn là các điểm giám sát của ~v~. Riêng với ~v = S~, đường đi có độ dài bằng ~0~ chỉ chứa máy chủ ~S~.

Với mỗi máy chủ ~v~, hãy xác định số điểm giám sát của ~v~.

Dữ liệu vào

Vào từ file văn bản NETWATCH.INP gồm:

• Dòng đầu tiên chứa ba số nguyên ~N, M, S~ (~1 \leq N \leq 2 \cdot 10^5~, ~0 \leq M \leq 2 \cdot 10^5~, ~1 \leq S \leq N~).
• Trong ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ (~1 \leq u, v \leq N~, ~u \neq v~), cho biết có một kênh truyền hai chiều nối trực tiếp hai máy chủ ~u~ và ~v~.
• Giữa hai máy chủ có nhiều nhất một kênh truyền trực tiếp.
• Dữ liệu bảo đảm có thể truyền dữ liệu từ ~S~ đến mọi máy chủ.

Dữ liệu ra

Ghi ra file văn bản NETWATCH.OUT kết quả theo yêu cầu sau:

• In ra ~N~ số nguyên. Số thứ ~v~ là số điểm giám sát của máy chủ ~v~.

Ví dụ 1

Input

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

Output

1 2 2 2 3 3 3

Giải thích

Có hai đường đi ngắn nhất từ máy chủ ~1~ đến máy chủ ~4~:

$$ 1 \rightarrow 2 \rightarrow 4 $$

và

$$ 1 \rightarrow 3 \rightarrow 4. $$

Chỉ máy chủ ~1~ và máy chủ ~4~ xuất hiện trên cả hai đường đi, nên máy chủ ~4~ có ~2~ điểm giám sát.

Mọi đường đi ngắn nhất từ máy chủ ~1~ đến máy chủ ~7~ đều đi qua các máy chủ ~1, 4, 7~. Vì vậy, máy chủ ~7~ có ~3~ điểm giám sát.

Ràng buộc

• Subtask 1 (20%): ~M = N - 1~.
• Subtask 2 (25%): ~N, M \leq 2000~.
• Subtask 3 (25%): Khoảng cách ngắn nhất từ ~S~ đến mọi máy chủ không vượt quá ~50~.
• Subtask 4 (30%): Không có ràng buộc nào thêm.