版权声明

本题版权归 Long Long OJ 所有。

题目背景

在遥远的 KingCoder 王国，一场智障流感爆发了。

题目描述

KingCoder 王国里有 $n$ 位居民，他们有 $m$ 对双向的朋友关系。

每个人在发病的第二天上午会痊愈，获得免疫性。他在第二天中午和下午就不会感染，但是第二天晚上免疫性就会消失，可以被感染。

每天下午，每个当时发病的人的每一个朋友都会来看望他。而那些当时没有免疫性的倒霉蛋就会感染病毒，并在感染的第二天中午发病。

现在国王告诉了你每对朋友关系 $(u_i, v_i)$ 和在第一天中午发病的人 $s$，求最后一个发病的人在第几天中午被感染？

输入格式

第一行三个正整数 $n, m, s\ (1 \le n, m \le 10^5, 1 \le s \le n)$。

接下来 $m$ 行，每行两个正整数 $u_i, v_i\ (1 \le u_i, v_i \le n)$。

数据中同一个 $\bm{(u_i, v_i)}$ 可能出现多次，且 $\bm{(u_i, v_i)}$ 和 $\bm{(v_i, u_i)}$ 可能会同时出现。

数据中存在 $\bm{u_i = v_i}$ 的情况，此时该病人发病当天下午也会看望自己，但第二天上午正常痊愈并获得免疫力。

输出格式

输出共一行，表示最后一个发病的人在第几天中午被感染。

如果可以无限传染下去，请输出 $-1$。

样例

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

3

样例解释