Có ~N~ quả pháo được nối với nhau bằng ~M~ sợi dây. Khi một quả pháo phát nổ, lửa sẽ cháy qua các dây nối với quả pháo đó và làm cho các quả pháo nối với nó phát nổ. Giả sử thời gian để lửa truyền từ một quả pháo đến một quả pháo được nối với nó là ~1~ giây, hãy tính thời gian để tất cả các quả pháo phát nổ khi quả pháo thứ ~x~ nổ đầu tiên.

Input

• Dòng đầu chứa ~3~ số nguyên dương ~N, M, x~ ~(1 \le N \le 10^5, 0 \le M \le 10^5, 1 \le x \le N)~.
• ~M~ dòng sau, mỗi dòng chứa hai số nguyên dương ~i, j~ ~(1 \le i, j \le N)~ nghĩa là có một sợi dây nối giữa hai quả pháo thứ ~i~ và ~j~. Dữ liệu đảm bảo không có hai quả pháo nào được nối với nhau bằng hơn một dây.

Output

In ra một số nguyên là thời gian để tất cả các quả pháo phát nổ khi quả pháo thứ ~x~ nổ đầu tiên, hoặc ~-1~ nếu không thể nổ tất cả ~N~ quả pháo.

Sample

Input

1 0 1

Output

0

Giải thích: Ngay khi quả phảo thứ ~1~ phát nổ thì tất cả ~N~ quả pháo đều đã phát nổ.

Input

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

Output

3

Input

3 1 3
2 3

Output

-1