접촉 추적

신종 바이러스 감염이 확산되고 있다. 이 바이러스는 증상 유무와 관계없이 보균자와 밀접 접촉하면 전파되는 것으로 알려져 있다. 따라서 감염이 확정된 사람이나 감염 가능성이 높다고 판단된 사람과 밀접 접촉한 사람을 찾아 검사하는 것이 방역에 효과적이다. 이를 위해 휴대 전화 애플리케이션으로 모든 밀접 접촉 사건을 항상 기록하고, 감염이 확인되면 그 기록을 바탕으로 직간접 감염 위험이 있는 사람을 모두 찾아내는 시스템이 요구된다.

당신은 이런 시스템의 개발을 의뢰받았고, 휴대 전화 부분은 이미 완성했다. 설치된 애플리케이션이 같은 애플리케이션이 설치된 휴대 전화를 가진 다른 사람과의 밀접 접촉 사건을 감지하면 두 사람의 ID를 감시 센터로 보낸다.

다음 과제는 사용자의 감염이 확인되었을 때, 감염자로부터 직간접 전파 위험이 있는 사용자를 찾아내는 프로그램을 개발하는 것이다.

시스템 사용자의 감염이 확인되면, 일정 기간(전염 가능 기간) 안에 감염자와 밀접 접촉한 사용자가 감염 의심자로 분류된다. 감염 의심자가 그 감염 가능 사건 이후에 또 다른 사용자와 밀접 접촉했다면, 그 사용자도 감염 의심자가 된다. 의심자는 이런 방식으로 반복적으로 전파된다.

사용자의 감염이 확인되었을 때, 그 사용자의 ID와 감염자가 보균자가 될 가능성이 있는 시각 이후에 일어난 모든 사용자 간의 모든 밀접 접촉 사건 목록이 주어진다. 주어진 목록의 모든 사건은 감염자의 전염 가능 기간 안에 있다고 가정한다. 출력은 감염자로부터 직간접적으로 바이러스가 전파되었을 가능성이 있는 사용자의 수이다.

입력은 여러 데이터셋으로 이루어지며, 각 데이터셋은 다음 형식이다.

m n p a1 b1 … an bn

각 데이터셋은 세 정수로 시작한다. m (1 ≤ m ≤ 100)은 사용자의 수, n (0 ≤ n ≤ 1000)은 목록에 있는 사건의 수, p (1 ≤ p ≤ m)는 감염이 확인된 사용자의 ID이다.

다음 n줄에는 사용자 간의 밀접 접촉 사건이 시간 순서대로 한 줄에 하나씩 주어진다. 각 줄은 ID가 ai와 bi인 사용자가 밀접 접촉했음을 나타낸다. 여기서 ai와 bi는 1 ≤ ai ≤ m, 1 ≤ bi ≤ m, ai ≠ bi를 만족한다.

입력의 끝은 세 개의 0이 있는 줄로 표시된다. 데이터셋의 수는 50을 넘지 않는다.

각 데이터셋에 대해, 감염이 확인된 사용자와 그 사용자로부터 직간접적으로 바이러스가 전파되었을 가능성이 있는 사용자를 모두 포함한 총 사용자 수를 한 줄에 출력한다.