import java.util.*;
public class Main3 {
static boolean visit[];
static String result;
static List<String> list = new ArrayList<>();
static List<String> back = new ArrayList<>();
static boolean count;
// static String tickets[][]= {{"ICN", "JFK"}, {"HND", "IAD"}, {"JFK", "HND"}};
static String tickets[][]= {{"ICN", "SFO"}, {"ICN", "ATL"}, {"SFO", "ATL"}, {"ATL", "ICN"}, {"ATL","SFO"}};
// static String tickets[][]= {{"ICN", "SFO"}, {"SFO", "ATL"}, {"ICN", "ATL"}, {"ATL", "ICN"}, {"ATL","SFO"}};
public static void main(String[] args) {
for (String s : solution(tickets))
System.out.print(s + " ");
}
public static String[] solution(String[][] tickets) {
String[] answer = {};
visit = new boolean[tickets.length];
////////////////////////////////////
int[] tmp = new int[10000];
int n = 0, i;
for (i = 0; i < tickets.length; i++) {
if (tickets[i][0].equals("ICN")) {
tmp[n++] = i;
//System.out.println("tmp:" + tmp[i] + " n:" + n);// 0,1/1,2
} // tickets[i]는 ["INC"," "]형태
}
// for (int j = 0; j < n; j++) {
// System.out.println("INC " + tmp[j]);
// }
int a = 0;
for (int j = 0; j < n; j++) {
if (tickets[a][1].compareTo(tickets[tmp[j]][1]) > 0)//S>A
a = tmp[j];
}
System.out.println("start index = " + a);
// i=[INC,B] 중에서 알파벳순서가 맨 앞인 B를가진 티켓의 위치;
//////////////////////////////////////////////////
visit[a] = true;
list.add(tickets[a][0]);
dfs(tickets, tickets[a][1], 1);
answer = list.toArray(new String[list.size()]);
return answer;
}
public static void dfs(String[][] tickets, String end, int cnt) {
list.add(end);
for (int i = 0; i < tickets.length; i++) {
if (end.equals(tickets[i][0]) && !visit[i]) {
visit[i] = true;
dfs(tickets, tickets[i][1], cnt + 1);
}
}
}
}