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 friendship relationships among them.

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

Each day, every friend of a sick person will visit them. Those unlucky ones without immunity will be infected with the virus and fall ill on the day after infection.

Now the king has told you all the friendship pairs $(u_i,v_i)$ and the person $s$ who fell ill on the first day. Your task is to find the maximum number of days the virus can spread.

Input Format

The first line of input contains three integers $n, m, s$. The next $m$ lines each contain two integers $u_i, v_i$.

Output Format

Output a single line containing the maximum number of days the virus can spread. 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

Data Range

For 100% of the data: $1\le n,m\le 10^5$, $1\le u_i,v_i,s\le n$.