CIRCUITS - Circuits

no tags 

Original statement in spanish at

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.


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.


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.



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



hide comments
Vinicius Zibetti Resko [UNITAU]: 2015-12-09 18:45:00

I agree with you, it is not a simple graph problem.

Cheran Wu: 2013-09-17 17:30:40

The test data seems weak, my solution gets AC but prints 0 for the test case:

7 8
1 2
2 3
1 3
3 4
4 5
5 6
6 7
5 7

Douglas Ferlini Bastos Machado[UNB]: 2011-11-19 20:21:59

its not a simple graph problem

Last edit: 2011-11-22 02:55:18
[Trichromatic] XilinX: 2011-10-18 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: 2011-10-17 21:52:25

Nice task, but isn't this problem NP-hard ?
Please clarify if im wrong

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