고속버스 노선
시간 제한1초메모리 제한128 MB
세 나라 도시들 사이에 주어진 N개의 출발-도착 노선에 남은 도시들을 국가 제약을 지키며 중간 정류지로 배정해 완성된 노선을 출력하는 문제입니다.
문제
세 국가 A, B, C가 서로 국경을 맞대고 있다. 각 국가에는 1번부터 N번까지 N개의 도시가 있다. 총 3N개의 도시 중 입력으로 주어지는 2N개의 도시는 N개 노선의 출발지 또는 도착지이고, 나머지 N개의 도시는 노선의 중간 경유지로 정확히 한 번씩 사용해야 한다.
각 노선의 출발지와 도착지는 미리 주어지며, 두 도시는 서로 다르다. 도시 이름은 국가 이름과 번호를 공백 없이 붙여 쓴다. A1은 A국의 1번 도시이고, B3은 B국의 3번 도시이다.
출력할 노선들은 다음 조건을 모두 만족해야 한다.
- 출발지 또는 도착지가 아닌 모든 도시는 정확히 하나의 노선에 중간 경유지로 포함되어야 한다.
- 한 노선은 중간 경유지를 0개 이상 2개 이하로 가질 수 있다. 중간 경유지의 국가는 그 노선의 출발지 국가 및 도착지 국가와 달라야 한다. 중간 경유지가 2개라면 두 경유지도 서로 다른 국가에 속해야 한다. 따라서 출발지와 도착지가 서로 다른 국가인 노선은 중간 경유지를 많아야 1개만 가질 수 있다.
- 출발지와 도착지가 같은 국가인 노선은 중간 경유지를 1개 이상 포함해야 한다.
입력으로 주어지는 출발지와 도착지 쌍에 대해서는 위 조건을 만족하는 노선 집합이 항상 존재한다. 가능한 노선 집합이 여러 가지라면 그중 아무거나 하나만 출력하라.
입력
첫째 줄에 각 국가의 도시 수를 나타내는 정수 N(1 ≤ N ≤ 50,000)이 주어진다.
둘째 줄부터 N개의 줄에는 각 노선의 출발지와 도착지가 공백으로 구분되어 주어진다.
출력
입력에 주어진 노선 순서대로 N개의 줄을 출력한다. 각 줄에는 해당 노선에 포함되는 도시 이름을 출발지부터 도착지까지 순서대로 출력한다. 같은 줄의 도시 이름 사이에는 공백을 하나씩 둔다.