Source

This problem is adapted from Long Long OJ. All rights reserved.

Problem Background

In the distant Kingdom of KingCoder, an outbreak of idiocy flu has occurred.

Problem Description

There are $n$ residents in the Kingdom of KingCoder, with $m$ pairs of mutual friendship relationships among them.

Everyone who falls ill will recover on the second morning and gain immunity. They will not be infected on the second noon and the second afternoon, but their immunity will disappear on the second night, making them susceptible to infection again.

Each afternoon, every friend of a person sick (then) will visit them. Those unlucky ones without immunity (then) will be infected with the virus and fall ill on the next noon.

Now the king has told you all the friendship pairs $(u_i,v_i)$ and the person $s$ who fell ill on the first noon. Your task is to find the ID of the day when the latest infection occur.

Input Format

The first line of input contains three positive integers $n, m, s\ (1 \le n, m \le 10^5, 1 \le s \le n)$.

Each of the next $m$ lines contains two positive integers $u_i, v_i\ (1 \le u_i, v_i \le n)$.

One relation $\bm{(u_i, v_i)}$ may occur multiple times, and the relations $\bm{(u_i, v_i)}$ & $\bm{(v_i, u_i)}$ may occur simultaneously.

Relations satisfying $\bm{u_i = v_i}$ may occur, in which the sick person will visit himself/herself but recover on the second morning and gain immunity normally.

Output Format

Output a single line containing the ID of the day (noon) when the latest infection occur.

If the virus can spread infinitely, output $-1$.

Samples

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

3

Sample Explanation