A group of people, joyfully jogging. CC BY-SA 4.0 by wal on Pixabay

In the weekend of 26–27 September, the 100 Bruggenloop (100 Bridges Run) takes place in Leiden. In the past few years, the $$$20\,\textrm{km}$$$ route across the 100 bridges has always been the same, but this year, the organization wants to offer more variety.

The city council has already approved a selection of roads to be closed for the race. To maximize the variety, the organization wants to create as many unique courses as the closed roads allow. Each course must form a cycle that starts and ends on the same road and does not reuse any road (it may reuse intersections). Of course, the different courses will have different numbers of bridges, which will contribute to the variety.

To make a course viable, it must include a start zone located on one of its roads. Since each course is a cycle, the start zone also serves as the finish zone. However, installing start zones is expensive, and having fewer of them creates a nicer atmosphere by letting more participants start together.

To support budget planning, determine the minimum number of start zones needed so that every course passes through at least one.

As an example, consider Sample Input 2. Having a single start zone on the edge between vertices $$$7$$$ and $$$8$$$ is not enough, because there is also a cycle along all the outer edges. Placing a second start zone in any of those edges makes sure that every course passes through a start zone.

Visualization of Sample Input 2, where two start zones are needed to cover all courses.