Ten years ago, Delhi Metro started its operation by opening the first line in central Delhi. The government received enormous response from various sections of society of Delhi. People started using Metro services so often that only after 6 months all the train coaches filled tightly by the travelers After 10 years now, Metro expanded so much that now it covers almost all the major areas of the city. Today around 6 different lines are running in different areas which are connecting not only Delhi but also other NCR regions to Delhi. Lakhs of people using Metro service every day and today it becomes one of the top 10 well known Metro networks all over the world.

 For this new line, Metro Planning team found various localities where metro stations can be built and they identified various L localities around Delhi where commercial agreements are established. Goods were traded between localities via road that had a commercial agreement It is possible to connect any two localities by a line segment in the city.

 Eventually, the MLAs of localities decided to organize this commerce. They designed a commerce route that connected every locality around the city. The route met the following requirements:

•  It could start in any of the localities, visited each of the locality around the city, and finally ended in another locality different from the starting locality. 
• The route visited each locality exactly once.
•  Every pair of consecutively visited localities in the route had a commercial agreement. 
• Every pair of consecutively visited localities in the route was connected by a line segment. 
• To avoid crashes on route via road, the route never crossed itself

The figure shows the city and the localities around in it in different parts of city. The lines (both thick and thin) represent commercial agreements between localities. The thick lines represent a commerce route starting in locality 2 and ending in locality 5. This route never crosses itself. It would not be legal, for example, to construct a route that went from 2 to 6 to 5 to 1, since the route would cross itself. 

Localities in the city are numbered from 1 through L moving in clockwise direction.

Input Format

 Input 1: It will be the integer that tells the number of localities L in the city 

Input 2. It will be the integer that represents the number of commercial agreements, N 

Input 3: It will be the multi-dimensional integer array where:

 First line tell the number of rows 

Second line tell the number of columns Each Next N lines represents a unique commercial agreement between localities. 

Every line contains two space-separated integers that represent the two localities involved in the agreement. 

c1 c2

c1 c2

Constraints :

3

1<=N=50

Output Format 

It will be the integer array representing the order in which the localities are visited in the commerce route. 

Note: If it's not possible to construct a commerce route that meets all the requirements, return an array having -1 as only element.

Transcribed Image Text:

2. 7. 6. 2. 7. 6.

Answer rating: 100% (QA)

import javautilArrays import javautilScanner public class RouteFinder public static void intializein... View the full answer