고속버스노선

시간제한 : 1000ms

문제설명>

세 국가 A, B, C는 서로 국경을 마주하고 있으며, 각 국가에는 N개의 도시들이 있다. 이들 도시들에 대하여 국경을 통과하는 고속버스 노선을 N개 만들려고 한다. 전체 3N개의 도시들 중에서 2N개의 도시들은 노선의 출발지 또는 도착지로 하고, 나머지 N개의 도시들은 어떤 노선의 중간 경유지가 되도록 고속버스 노선을 정하려고 한다. N개의 각 노선의 (출발지, 도착지)는 미리 주어져 있으며 각 노선의 출발지와 도착지는 서로 다르다. 이 때, 정하고자 하는 노선들은 다음 조건들을 모두 만족해야 한다.
(1) 출발지 또는 도착지가 아닌 도시는 임의의 노선의 중간 경유지가 될 수 있고 반드시 어떤 노선의 중간 경유지로 포함되어야 하며, 하나의 노선에만 포함될 수 있다.
(2) 하나의 노선은 2개 이하의 중간 경유지를 갖는다. 노선에 중간 경유지를 포함할 때, 이 중간 경유지가 속한 국가는 출발지나 도착지가 속한 국가와는 달라야 한다. 그리고 노선의 중간 경유지가 2개인 경우에 이들 두 경유지는 모두 같은 국가에 속할 수 없다. (그러므로 출발지와 도착지가 서로 다른 국가에 속하는 노선은 많아야 1개의 중간 경유지만 가질 수 있다.)
(3) 출발지와 도착지가 같은 국가에 속한 노선은 반드시 1개 이상의 중간 경유지를 포함해야 한다.
각 도시의이름은 국가이름과 번호로 나타낸다. (번호는 N 이하의 자연수) A1은 국가 A의 1번도시 이름이고, B3은 국가 B의 3번도시의 이름이다. 여기서 국가 이름과 번호 사이에는 공백이 없다. 예를 들어 각 국가에 3개의 도시가 있다고 하자. 그리고 세 노선의 출발지, 도착지가 각각 (A1, B1) (A2, A3) (B2, C2)라 하자. 그러면 세 개의 노선을 다음과 같이 만들 수 있다. 노선 1 : A1 -> C1 -> B1 노선 2 : A2 -> B3 -> C3 -> A3 노선 3 : B2 -> C2 출발지와 도착지의 쌍이 N개 주어진 경우, 위의 조건들을 만족하는 고속버스 노선들을 항상 정할 수 있다. 이러한 노선들을 출력하는 프로그램을 작성하시오. 만약 위의 조건을 만족하는 고속버스 노선들이 여러개 일 경우 임의의 하나만 출력해도 된다.

입력설명>

첫째 줄에는 도시들의 개수를 나타내는 정수 N(1≤N≤50,000) 이 주어진다. 둘째 줄부터 N+1 번째 줄까지 각 줄에 노선의 출발지와 도착지가 공백을 사이에 두고 주어진다.

출력설명>

첫째 줄부터 N번째 줄까지 입력에 주어진 노선 순서대로 각 줄에 해당 노선에 포함되는 도시들의 이름을 출발지부터 도착지까지 순서대로 출력한다. 한 노선에 속하는 도시이름과 도시이름 사이에는 공백을 하나 둔다.

입출력예시1>

입력
3
A1 B1
A2 A3
B2 C2

출력
A1 C1 B1
A2 B3 C3 A3
B2 C2

출처 : KOI-2004전국고등기출