고속버스 노선

세 국가 A, B, C가 서로 국경을 맞대고 있다. 각 국가에는 1번부터 N번까지 N개의 도시가 있다. 총 3N개의 도시 중 입력으로 주어지는 2N개의 도시는 N개 노선의 출발지 또는 도착지이고, 나머지 N개의 도시는 노선의 중간 경유지로 정확히 한 번씩 사용해야 한다.

각 노선의 출발지와 도착지는 미리 주어지며, 두 도시는 서로 다르다. 도시 이름은 국가 이름과 번호를 공백 없이 붙여 쓴다. A1은 A국의 1번 도시이고, B3은 B국의 3번 도시이다.

출력할 노선들은 다음 조건을 모두 만족해야 한다.

1. 출발지 또는 도착지가 아닌 모든 도시는 정확히 하나의 노선에 중간 경유지로 포함되어야 한다.
2. 한 노선은 중간 경유지를 0개 이상 2개 이하로 가질 수 있다. 중간 경유지의 국가는 그 노선의 출발지 국가 및 도착지 국가와 달라야 한다. 중간 경유지가 2개라면 두 경유지도 서로 다른 국가에 속해야 한다. 따라서 출발지와 도착지가 서로 다른 국가인 노선은 중간 경유지를 많아야 1개만 가질 수 있다.
3. 출발지와 도착지가 같은 국가인 노선은 중간 경유지를 1개 이상 포함해야 한다.

입력으로 주어지는 출발지와 도착지 쌍에 대해서는 위 조건을 만족하는 노선 집합이 항상 존재한다. 가능한 노선 집합이 여러 가지라면 그중 아무거나 하나만 출력하라.

첫째 줄에 각 국가의 도시 수를 나타내는 정수 N(1 ≤ N ≤ 50,000)이 주어진다.

둘째 줄부터 N개의 줄에는 각 노선의 출발지와 도착지가 공백으로 구분되어 주어진다.

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