미스터리한 X 네트워크

면접 대비

시간 제한1초메모리 제한128 MB

요약
사람 N명의 무방향 그래프가 주어질 때, 두 사람 사이 최단 경로에 놓이는 중간 사람 수의 최솟값을 구한다.
난이도

보통10점 중 4점

유형
그래프, BFS, 최단 경로, 큐
정답자
아직 제출이 없습니다

문제

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

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

입력

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

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

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

출력

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

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

예제3

  1. 예제 1

    입력
    4
    0 3 1 2 3
    1 1 0
    2 2 0 3
    3 2 0 2
    1 2
    
    예상 출력
    1 2 1
    
  2. 예제 2

    입력
    2
    0 1 1
    1 1 0
    0 1
    
    예상 출력
    0 1 0
    
  3. 예제 3

    입력
    5
    0 1 1
    1 2 0 2
    2 2 1 3
    3 2 2 4
    4 1 3
    0 4
    
    예상 출력
    0 4 3