Five friends are planning an adventure trip across a scenic country filled with mountains, forests, and lakes. The country is divided into N places (labeled 1 to N), which are connected by M bidirectional roads. The friends want their trip to be as adventurous as possible — that is, they want to see as much of the country as possible without taking the same road twice. They can start the trip from any place, but need to end the trip at Place 1. They can choose to skip certain places or roads. They can also visit a place multiple times, but will not go through a road more than once.

Given the above constraints, write a program to find the maximum number of roads the friends can go through in a single trip.

Read the input from STDIN and print the output to STDOUT. Do not print arbitrary strings anywhere in the program, as these contribute to the output and test cases will fail.