19649번 - 미담 전하기

인성에 문제가 없는 이상원은 평소 주변인에 대한 미담을 자주 하곤 한다. 사람들의 인간관계는 복잡하게 얽혀 있어, 누군가에게 어떤 사람에 대한 미담을 하면 돌고 돌아 그 대상자의 귀에 들어가게 된다.

인간관계와 미담은 다음과 같이 정의할 수 있다.

• 인간관계는 일방적인 관계이다. 즉, A → B이어도 B → A가 성립하지 않을 수 있다.
• 인간관계 A → B가 주어졌을 때 B는 A와 친한 사람 중 한 명에 속한다.
• 각각의 사람들은 미담을 여러 번 전해 들을 수 있다. 어떤 사람 A가 미담을 전해 들었다면, 그때마다 A는 친한 사람 중 한 명을 골라 미담 건네주기를 한다.

미담이라는 것은 당사자에게 전달되었을 때 비로소 아름다운 것. A로부터 시작된 미담이 제3자 C에게 전파되었을 때, C에 의해서도 당사자에게 전달될 수 있다면 A를 '직접 미담 전파자'라 하고, C를 '간접 미담 전파자'라고 한다. '미담 당사자'에 의해서도 '간접 미담 전파자'가 생길 수 있고, '미담 당사자' 또한 '간접 미담 전파자'가 될 수 있다. '직접 미담 전파자'는 '간접 미담 전파자'가 될 수 없다.

다음과 같은 관계가 주어졌을 때 '미담 당사자'가 3번, '직접 미담 전파자'를 1번이라 하면 '간접 미담 전파자'는 {2}로 1명이다.

상원이는 '미담 당사자' K에 관한 미담을 전파하고 싶다. 한편으로는 여러 사람에게 말하고 싶은 생각도 없었기에 '직접 미담 전파자' 한 명에게만 전하고자 한다. '직접 미담 전파자' X (X ≠ K)를 정해서 미담 전파를 했을 때 '간접 미담 전파자'가 최대 몇 명이나 생길 수 있을까?

첫 번째 줄에 N (1 ≤ N ≤ 10,000), M (0 ≤ M ≤ 100,000)이 주어진다. 이는 각각 사람의 수, 인간관계의 수를 의미한다.

두 번째 줄부터 M + 1 번째 줄까지 M개의 줄에 걸쳐 인간관계의 정보가 주어진다. 각 줄은 두개의 정수 u, v (1 ≤ u, v ≤ N, u ≠ v)가 공백으로 구분되어 주어진다. 이는 u → v 인 인간관계를 의미한다. 같은 인간관계가 두 번 주어지는 경우는 없다.

마지막 줄에 정수 K (1 ≤ K ≤ N)이 주어진다. 이는 미담 당사자를 의미한다.

첫 번째 줄에 문제에서 설명한 X와, X에 의해 생기는 '간접 미담 전파자'의 수를 공백으로 구분하여 출력한다. X에 해당하는 값이 여러 개라면, 그 중에 가장 작은 정수를 출력한다. '간접 미담 전파자'가 생길 수 없다면 첫 번째 줄에 0을 출력한다.

1번 사람에게 미담을 전파하면 전파 과정은 1→2→3→1→2→4→5→6→7→8→7로, 인해 생기는 '간접 미담 전파자'는 {2, 3, 4, 5, 6, 7, 8}로 7명이다.