2603번 - 고속버스 노선 스페셜 저지

문제

세 국가 A, B, C는 서로 국경을 마주하고 있으며, 각 국가에는 N개의 도시들이 있다. 이들 도시들에 대하여 국경을 통과하는 고속버스 노선을 N개 만들려고 한다. 전체 3N개의 도시들 중에서 2N개의 도 시들은 노선의 출발지 또는 도착지로 하고, 나머지 N개의 도시들은 어떤 노선의 중간 경유지가 되도록 고속버스 노선을 정하려고 한다. N개의 각 노선의 (출발지, 도착지)는 미리 주어져 있으며, 각 노선의 출발지와 도착지는 서로 다르다. 이때, 정하고자 하는 노선들은 다음 조건들을 모두 만족해야 한다.

1. 출발지 또는 도착지가 아닌 도시는 임의의 노선의 중간 경유지가 될 수 있고, 반드시 어떤 노선의 중간 경유지로 포함되어야 하며, 하나의 노선에만 포함될 수 있다.
2. 하나의 노선은 2개 이하의 중간 경유지를 갖는다. 노선에 중간 경유지를 포함할 때, 이 중간 경유지가 속한 국가는 출발지나 도착지가 속한 국가와는 달라야 한다. 그리고 노선의 중간 경유지가 2개인 경우에 이들 두 경유지는 모두 같은 국가에 속할 수 없다. (그러므로 출발지와 도착지가 서로 다른 국가에 속하는 노선은 많아야 1개의 중간 경유지만 가질 수 있다.)
3. 출발지와 도착지가 같은 국가에 속한 노선은 반드시 1개 이상의 중간 경유지를 포함해야 한다. 각 도시의 이름은 국가이름과 번호로 나타낸다 (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번째 줄까지 입력에 주어진 노선 순서대로 각 줄에 해당 노선에 포함되는 도시들의 이름을 출발지부터 도착지까지 순서대로 출력한다. 한 노선에 속 하는 도시이름과 도시이름 사이에는 공백을 하나 둔다.

제한

힌트