29810번 - 배신자

문제

김한양은 아웃사이더, 일명 아싸이다. 한 마디로, 친구가 별로 없다. 주변을 둘러보니 인싸(인사이더, 각종 행사나 모임에 적극적으로 참여하면서 사람들과 잘 어울려 지내는 사람을 이르는 말)인 동기들이 많이 보인다. 가만히 보니, 동기들은 이미 파가 갈려 몰려다니고 있다. 여기에서, '파'란 친구 관계로 연결된 사람들의 모임을 이르는 말이다. 친구의 친구도 같은 파로 간주하기 때문에, 파의 크기는 무한히 커질 수도 있다. 김한양은 최대한 빨리 많은 친구를 사귀고 싶기 때문에, 가장 인원수가 많은 파에 들어가고 싶다.

그런데, 동기들 중에는 배신자가 한 명 있다. 배신자는 본인이 속한 파 내에서 정치질을 하여 두루두루 친하게 지내지 못하게 하고, 본인을 중심으로 파를 갈기갈기 찢어 놓는다. 예를 들어, 1ドル$과 2ドル,ドル 2ドル$와 3ドル,ドル 3ドル$과 4ドル,ドル 4ドル$와 5ドル$가 서로 친구이고, 배신자가 2ドル$라고 하자. 겉으로 보기에는 $(1, 2, 3, 4, 5)$가 한 파 같아 보이지만, 이들은 $(1, 2)$의 조합과 $(2, 3, 4, 5)$의 조합으로밖에 어울려 다니지 못한다. 파가 둘로 쪼개지는 것이다.

만약, 친구 관계가 계속 연결되다가 배신자가 포함된 사이클을 형성하게 된다면, 사이클에 속한 친구들끼리 배신자의 배신 행태를 공유하여 배신자를 파에서 쫓아낸다. 예를 들어, $(1, 2), (2, 3), (3, 1), (3, 4)$의 친구 관계가 있다고 하자. 3ドル$이 배신자일 때, 1,ドル 2$는 서로 정보를 공유하여 그들의 그룹에서 배신자인 3ドル$을 축출한다. 결국 이들은 $(1, 2)$의 조합과 $(3, 4)$의 조합인 파 2ドル$개로 나뉜다.

배신자가 모든 파에서 축출되면, 배신자는 친구가 없이 홀로 다녀야 하기 때문에 크기가 1ドル$인 파가 된다.

동기들의 친구 관계와 배신자가 주어졌을 때 가장 크기가 큰 파의 인원수를 알아내어 김한양을 도와주자. $A$가 $B$를 친구라고 여긴다면 $B$도 $A$를 친구로 여기며, 주어지는 친구 관계에 중복은 없다. 또한, 자기 자신과 친구를 맺는다고 말하지는 않기 때문에 서로 다른 사람을 잇는 친구 관계만 주어진다.

입력

첫째 줄에 $N(1 ≤ N ≤ 200,000円)$과 $M(1 ≤ M ≤ 200,000円)$이 주어진다. $N$은 동기의 수, $M$은 친구 관계 정보의 개수이다.

둘째 줄부터 $M$개의 줄에 걸쳐 두 정수 $A$와 $B$가 공백을 두고 주어진다. 이는 동기 $A$와 동기 $B$가 서로 친구라는 의미이다.

마지막 줄에 배신자의 번호 $X(1 \le X \le N)$가 주어진다.

출력

크기가 가장 큰 파의 인원수를 출력한다.

제한

힌트