Below is the complete Java program for this work.
import java.util.*;
public class Source {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// Get the number of tickets from input
int n = in.nextInt();
// Map to store all the tickets
Map<String, String> tickets = new HashMap<>();
// Store the source and destination of the tickets to the map "tickets"
for (int i = 0; i < n; i++) {
tickets.put(in.next(), in.next());
in.nextLine();
}
// Find the start of the itinerary
String startCity = findStartCity(tickets);
// Print the itinerary
printItinerary(startCity, tickets);
}
// Helper method to find the start city
private static String findStartCity(Map<String, String> tickets) {
Set<String> sources = new HashSet<>(tickets.keySet());
Set<String> destinations = new HashSet<>(tickets.values());
sources.removeAll(destinations);
if (sources.size() == 1) {
return sources.iterator().next();
} else {
return "Invalid";
}
}
// Helper method to print the itinerary
private static void printItinerary(String startCity, Map<String, String> tickets) {
List<String> itinerary = new ArrayList<>();
String currentCity = startCity;
while (currentCity != null) {
itinerary.add(currentCity);
currentCity = tickets.get(currentCity);
}
if (itinerary.size() == 1) {
System.out.println("Invalid");
} else {
for (String city : itinerary) {
System.out.print(city + " ");
}
}
}
}