광석 운반

관리자 셀프리지(Selfridge)는 판도라 행성의 채굴 경로를 분석하고 있다. 그는 광산들 사이의 연결 관계를 그래프로 수집했다. 최신 광석 운반선은 정확히 3개의 채굴 캠프를 방문할 수 있다. 다시 말해, 어떤 광산에서 출발하여 정확히 2번 이동하여 도달하는 광산까지 갈 수 있다.

각 질의 광산에 대해, 그 광산에서 정확히 2번 이동해야만 도달할 수 있는(그보다 적은 이동으로는 도달할 수 없는) 광산들, 즉 최단 이동 횟수가 정확히 2인 광산들을 모두 찾아라.

광산들 사이의 연결은 양방향이다.

입력은 하나 이상의 서로 독립적인 문제 인스턴스로 이루어진다.

각 인스턴스는 GRAPH BEGIN 줄로 시작한다. 그다음 줄들에는 광산(정점)과 그 광산에 인접한 광산(간선)들이 나열된다. 각 줄은 하나의 광산 이름으로 시작하고, 같은 줄에 그 광산과 연결된 이웃 광산들의 이름이 이어진다. GRAPH END 줄이 그래프 설명의 끝을 나타낸다.

그 뒤로는 답을 계산해야 하는 질의 광산들이 한 줄에 하나씩 나열된다. 이 질의 목록 다음에는 완전히 새로운 문제 인스턴스가 GRAPH BEGIN부터 다시 시작될 수 있으며, 각 인스턴스는 서로 독립적으로 처음부터 다시 구성된다.

어떤 광산은 다른 광산의 이웃으로만 등장하고, 별도의 줄로 설명되지 않을 수도 있다. 광산 이름은 공백을 포함하지 않는 임의의 문자열이다.

분석 대상인 각 질의 광산마다 한 줄씩 출력한다. 각 줄에는 해당 광산에서 정확히 2번 이동해야만 도달할 수 있는(그보다 적은 이동으로는 도달할 수 없는) 광산들의 이름을 사전순으로 출력하며, 각 이름 뒤에 공백을 하나씩 붙인다. 그러한 광산이 하나도 없으면 빈 줄을 출력한다.