You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Một tòa nhà có $n$ phòng học, được nối với nhau bởi một số hành lang hai chiều. Hai phòng học được gọi là liền kề nếu có hành lang nối trực tiếp giữa chúng.

Mỗi phòng học có một số điện thoại nội bộ. Nếu hai phòng học liền kề có cùng chữ số cuối của số điện thoại, người ta gọi đó là cặp phòng dễ nhầm.

Giả sử bạn đang ở một phòng học $s$. Bạn chỉ được đi qua những hành lang nối giữa các cặp phòng dễ nhầm.

Yêu cầu

Hãy cho biết có bao nhiêu phòng có thể đi tới được từ phòng $s$ (tính cả phòng $s$), nếu bạn chỉ được đi qua các hành lang nối giữa những cặp phòng dễ nhầm.

Dữ liệu

Vào từ đầu vào chuẩn:

• Dòng 1: ba số nguyên dương $n, m, s$ ($1 \le s \le n$) — số phòng học, số hành lang và phòng xuất phát.
• Dòng 2: $n$ số nguyên dương (không bắt đầu bằng chữ số 0, giá trị $\le 10^9$) là số điện thoại của từng phòng, theo thứ tự từ phòng 1 đến phòng $n$.
• $m$ dòng tiếp theo: mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le n$) — biểu thị có hành lang hai chiều nối giữa phòng $u$ và phòng $v$.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả

In ra một số nguyên là số phòng có thể đi tới được từ phòng $s$ (kể cả phòng $s$), nếu chỉ đi qua các hành lang nối giữa những cặp phòng dễ nhầm.

Ví dụ

5 5 1
13 23 44 36 27
1 2
2 3
3 4
4 5
2 5

2

Giới hạn

Subtask 1 (50% số điểm): $n, m \le 10^3$.

Subtask 2 (50% số điểm): $n, m \le 10^5$.