Company: Goldman Sachs_10july
Difficulty: medium
Maximum Roads in Adventure Trip Problem Description Five friends are planning an adventure trip across a scenic country of mountains, forests and lakes. The country is divided into N places, numbered 1 to N, joined by M two-way roads. The friends want the trip to be as adventurous as possible, which means using as many roads as they can. Their trip must obey these rules: The trip is one unbroken journey: it starts at some place, and each following step moves along a road from the place the friends are currently in to the place at the other end of that road. The trip may start at any place, but it must finish at place 1. No road may be travelled more than once, in either direction. A place may be passed through any number of times. Roads and places may be skipped; the friends need not cover the whole country. Write a program that prints the largest number of roads a single such trip can use. Read the input from STDIN and print the output to STDOUT. Do not print any other text, as everyt