Morgan Stanley OA-10 2024

Problem Description

An organization is hosting an event with multiple stalls, each connected by one-directional roads. There are N stalls and the goal is to visit every road in such a way that all the stalls are visited without causing any congestion. Every road connects two stalls directly or indirectly via another stall. The organization needs to identify the optimal route that allows people to visit every stall by traversing each road exactly once.

You are tasked with writing an algorithm to find the optimal route for visiting all stalls based on their connections.

Input Format:

• The first line contains two space-separated integers:
  • grid_row: the number of rows N.
  • grid_col: the number of columns M.
• The next N lines each contain M space-separated integers, representing the IDs of stalls connected by a road.

Output Format:

• Print N lines of M space-separated integers representing the optimal route, such that each road is visited exactly once.

Constraints:

• The grid has exactly two columns (i.e. grid_col = 2 ).
• The roads are one-directional, and you need to find an optimal route.

Sample Input:

3 2
1 5
7 1
5 7

Sample Output:

1 5
5 7
7 1

Explanation:

The Optimal route is: The road starting with stall 1 will end at stall 5. The road starting with stall 5 will end at stall 7 which will be continued by the road starting with stall 7 and ending at stall 1.