미스터리한 X 네트워크

아직 제출이 없습니다시간 제한1초메모리 제한128 MB

문제

에콜 폴리테크니크(별명 “X”)는 카마라드(camarade) 네트워크로 유명하다. 카마라드란 같은 학교를 거쳐 간 동문을 뜻한다. 어떤 카마라드가 무언가(돈, 일자리 등)를 필요로 하면 이 네트워크에 도움을 청할 수 있다. 학번이 서로 다르더라도, 서로 아는 카마라드들을 중간에 거치면 원하는 상대에게 반드시 닿을 수 있다. 카마라드 관계는 대칭이며(서로 안다), 이 네트워크 덕분에 누구에게든 도달하는 경로가 항상 존재한다.

두 사람을 잇는 데 필요한 이러한 중간 카마라드의 수를 최소로 만드는 것이 목표다.

입력

첫째 줄에 카마라드의 수 NN (1N1051 \le N \le 10^5)이 주어진다. 카마라드에는 00부터 N1N-1까지 번호가 매겨져 있다.

이어지는 NN개의 줄은 각각 한 명의 카마라드를 설명한다. 각 줄은 그 카마라드의 번호 cc로 시작하고, 이어서 cc가 아는 카마라드의 수 ncn_c (nc<100n_c < 100), 그리고 그 ncn_c명의 번호가 온다. 한 줄의 모든 정수는 공백 하나로 구분된다.

마지막 줄에는 두 번호 c1c_1c2c_2 (c2c1c_2 \ne c_1)가 주어진다. c1c_1은 도움을 청하는 카마라드, c2c_2는 도움을 받고 싶은 상대다.

출력

공백으로 구분된 세 정수 c1c_1, c2c_2, 그리고 c1c_1에서 c2c_2에 도달하는 데 필요한 중간 카마라드의 최소 수를 출력한다.

중간 카마라드란 최단 경로에서 c1c_1c2c_2를 제외하고 그 사이에 있는 사람들을 말한다. 두 사람이 서로 직접 알고 있다면 이 값은 00이다.