시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 109 | 17 | 7 | 18.919% |
세 국가 A, B, C는 서로 국경을 마주하고 있으며, 각 국가에는 N개의 도시들이 있다. 이들 도시들에 대하여 국경을 통과하는 고속버스 노선을 N개 만들려고 한다. 전체 3N개의 도시들 중에서 2N개의 도 시들은 노선의 출발지 또는 도착지로 하고, 나머지 N개의 도시들은 어떤 노선의 중간 경유지가 되도록 고속버스 노선을 정하려고 한다. N개의 각 노선의 (출발지, 도착지)는 미리 주어져 있으며, 각 노선의 출발지와 도착지는 서로 다르다. 이때, 정하고자 하는 노선들은 다음 조건들을 모두 만족해야 한다.
예를 들어, 각 국가에 3개의 도시가 있다 하자. 그리고 세 노선의 출발지, 도착지가 각각 (A1, B1), (A2, A3), (B2, C2)라 하자. 그러면 세 개의 노선을 다음과 같이 만들 수 있다.
출발지와 도착지의 쌍이 N개 주어진 경우, 위의 조건들을 만족하는 고속버스 노선들을 항상 정할 수 있다. 이러한 노선들을 출력하는 프로그램을 작성하시오. 만약 위의 조건들을 만족하는 고속버스 노선들 의 집합이 여러 개일 경우 임의의 하나만 출력하면 된다.
첫째 줄에는 도시들의 개수를 나타내는 정수 N(1 ≤ N ≤ 50,000) 이 주어진다. 둘째 줄부터 N + 1번째 줄까지 각 줄에 노선의 출발지와 도착지가 공백을 사이에 두고 주어진다.
첫째 줄부터 N번째 줄까지 입력에 주어진 노선 순서대로 각 줄에 해당 노선에 포함되는 도시들의 이름을 출발지부터 도착지까지 순서대로 출력한다. 한 노선에 속 하는 도시이름과 도시이름 사이에는 공백을 하나 둔다.
3 A1 B1 A2 A3 B2 C2
A1 C1 B1 A2 B3 C3 A3 B2 C2