CIRCUITS  Circuits
Original statement in spanish at http://www.dc.uba.ar/events/icpc/download/problems/taip2011problems.pdf
Everyone is aware of the existence of the well known Nordenskjold Archipelago, located in the Arctic Ocean and belonging to the Krasnoyarsk Krai of Russia. This archipelago consists of a groups of N islands and M aquatic routes between some pairs of islands. Each route connects a pair of islands and for each pair there is at most one route connecting them.
Considering the popularity of Nordenskjold Archipelago, Krasnoyarsk's authorities are concerned about its touristic value. The touristic value of the archipelago is given by the total number of islands that belong to at least one “touristic circuit”. A touristic circuit is a path starting and ending in the same island that visits at least three different islands, never visits the same island more than once and uses just aquatic routes to go from one island to the next one.
Krasnoyarsk's authorities want to know the minimum number of additional aquatic routes that must be built so that every island belongs to at least one touristic circuit. Your task is to write a program that answers this question.
Input
The input contains several test cases. Each test case is described in several lines. The first line contains two integer numbers N and M (3 <= N <= 100, 1 <= M <= 1000) which indicate the number of islands and the number of aquatic routes, respectively. Each island is identified by a number between 1 and N. Each of the next M lines contains two integers U and V (1 <= U < V <= N), indicating that there is an aquatic route connecting islands U and V. You may assume that in each test case there is at most one aquatic route connecting the same pair of islands. The last line of the input contains the number 1 twice and should not be processed as a test case.
Output
For each test case output a single line with an integer representing the minimum number of additional aquatic routes that must be built so that every island belongs to at least one touristic circuit.
Example
Input:
3 1 1 3 9 10 1 2 2 3 1 3 7 9 5 9 5 7 6 8 4 6 4 8 8 9 4 4 1 2 1 4 1 3 2 3 12 9 1 7 2 6 4 9 9 10 8 12 1 5 1 8 8 11 4 10 1 1
Output:
2 0 1 4
hide comments
Vinicius Zibetti Resko [UNITAU]:
20151209 18:45:00
I agree with you, it is not a simple graph problem. 

Cheran Wu:
20130917 17:30:40
The test data seems weak, my solution gets AC but prints 0 for the test case:


Douglas Ferlini Bastos Machado[UNB]:
20111119 20:21:59
its not a simple graph problem Last edit: 20111122 02:55:18 

[Trichromatic] XilinX:
20111018 01:27:37
You are wrong. This problem only requires each vertex belongs to a simple cycle, but not all vertexes belong to one simple cycle. i.e. Two vertexes may belong to different cycles. 

Problem Solver:
20111017 21:52:25
Nice task, but isn't this problem NPhard ? http://en.wikipedia.org/wiki/Hamiltonian_completion

Added by:  Pablo Ariel Heiber 
Date:  20111004 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Argentinian Programming Tournament 2011 