TDZ đang muốn đi chơi. Thành phố của TDZ có \(N\) ngã tư đánh số từ \(1\) đến \(N\), và có \(M\) con đường hai chiều nối giữa các ngã tư này. Nhà của TDZ ở ngã tư số \(1\) và công viên nước ở ngã tư số \(N\). Xe của TDZ sắp hết xăng, và cần phải đi qua trạm xăng ở ngã tư số \(x\) để tiếp nhiên liệu.

Biết rằng sơ đồ đường đi trong thành phố tạo thành một đồ thị vô hướng, không cạnh bội, không có khuyên. Thời gian đi hết một con đường là \(1\) đơn vị. Hãy tìm đường đi ngắn nhất để TDZ có thể đi từ ngã tư số \(1\), đi qua trạm xăng và đến ngã tư số \(N\).

Input

• Dòng đầu tiên chứa ba số nguyên \(N, M, x\) (\(1 \leq N, M \leq 10^5; \; 1 \leq x \leq N; \; x \neq 1; \; x \neq N\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u, v\) mô tả đường đi \(2\) chiều giữa ngã tư \(u\) và ngã tư \(v\).

Output

• In ra số đơn vị thời gian ít nhất để đi như đề bài. Nếu không có đường đi thoả mãn, in ra -1.

Example

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

5