IOI '12  Sirmione/Montichiari, Italy
Parachute Rings
An early and quite sophisticated version of what we now call a parachute is described in Leonardo's Codex Atlanticus (ca. 1485). Leonardo's parachute consisted of a sealed linen cloth held open by a pyramidshaped wooden structure.
Linked rings
Skydiver Adrian Nicholas tested Leonardo's design more than 500 years later. For this, a modern lightweight structure tied Leonardo's parachute to the human body. We want to use linked rings, which also provide hooks for the sealed linen cloth. Each ring is made of flexible and strong material. Rings can be easily linked together as every ring can be opened and reclosed. A special configuration of linked rings is the chain. A chain is a sequence of rings in which each ring is only connected to its (at most two) neighbours, as illustrated below. This sequence must have a start and an end (rings that are connected to at most one other ring each). Specifically, a single ring is also a chain.
Other configurations are clearly possible, since a ring can be linked to three or more other rings. We say that a ring is critical if after opening and removing it, all remaining rings form a set of chains (or there are no other rings left). In other words, there can be nothing but chains left.
Example
Consider the 7 rings in the next figure, numbered from 0 to 6. There are two critical rings. One critical ring is 2: after its removal, the remaining rings form chains [1], [0, 5, 3, 4] and [6]. The other critical ring is 3: after its removal, the remaining rings form chains [1, 2, 0, 5], [4] and [6]. If we remove any other ring, we do not obtain a set of disjoint chains. For example, after removing ring 5: although we have that [6] is a chain, the linked rings 0, 1, 2, 3 and 4 do not form a chain.
Statement
Your task is to count the number of critical rings in a given configuration that will be communicated to your program.
At the beginning, there are a certain number of disjoint rings. You will first be given the number N, to communicate that there are N disjoint rings numbered from 0 to N  1 (inclusive) in the initial configuration. After that, rings are linked together. At any given time, you can be asked to output the number of critical rings in the current configuration. Specifically, you have to implement two operations:
Link A B
— the two rings numberedA
andB
get linked together. It is guaranteed thatA
andB
are different and not already linked directly; apart from this, there are no additional conditions on A and B, in particular no conditions arising from physical constraints. Clearly,Link A B
andLink B A
are equivalent.CountCritical
— output the number of critical rings for the current configuration of linked rings.
Input Format
Your program must read the input in the following format:
 line 1: N, L;
 lines 2, …, L + 1;

1
to invokeCountCritical
A B
parameters toLink
Sample Input and Description
Consider our figure with N = 7 rings and suppose that they are initially unlinked. We show a possible sequence of calls, where after the last call we obtain the situation depicted in our figure.
Input  Description  Output 

7 13  N = 7, L = 13 

1  CountCritical  7 
1 2  Link 1 2 

1  CountCritical  7 
0 5  Link 0 5 

1  CountCritical  7 
2 0  Link 2 0 

1  CountCritical  7 
3 2  Link 3 2 

1  CountCritical  4 
3 5  Link 3 5 

1  CountCritical  3 
4 3  Link 4 3 

1  CountCritical  2 
Subtask 1 [20% of points]
 N ≤ 5 000
 The operation
CountCritical
is called only once, after all the other calls; the operationLink
is called at most 5 000 times.
Subtask 2 [17% of points]
 N ≤ 1 000 000
 The operation
CountCritical
is called only once, after all the other calls; the operationLink
is called at most 1 000 000 times.
Subtask 3 [18% of points]
 N ≤ 20 000
 The operation
CountCritical
is called at most 100 times; the operationLink
is called at most 10 000 times.
Subtask 4 [14% of points]
 N ≤ 100 000
 The operations
CountCritical
andLink
are called, in total, at most 100 000 times.
Subtask 5 [31% of points]
 N ≤ 1 000 000
 The operations
CountCritical
andLink
are called, in total, at most 1 000 000 times.
All Submissions
Best Solutions
Point Value: 25 (partial)
Time Limit: 5.00s
Memory Limit: 256M
Added: Aug 12, 2013
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
It's quiet in here...