Parachute Rings

Time limit3sMemory limit128 MB

Summary
Process link operations on a growing undirected graph and, after each query, count the vertices whose removal leaves only paths (or nothing).
Level

Medium7 of 10

Topics
Graph, Union-find, Implementation, Dynamic programming
Solved
No attempts yet

Problem

Leonardo da Vinci's Codex Atlanticus describes the first fairly sophisticated parachute ever designed: an umbrella-shaped sheet of linen stretched over a pyramid-shaped wooden frame.

The skydiver Adrian Nicholas actually tested this more-than-500-year-old design, using a modern ultralight structure to strap a person to the parachute. We want to use a structure of rings that can also be hooked onto the linen. Each ring is made of a flexible but strong material, and every ring can be opened and closed, so it can be freely connected to other rings.

A chain is a special shape of ring structure. As in the figure below, when the rings are connected one after another, each to at most two neighboring rings, forming a single line with a start and an end, the structure is a chain. The rings at the start and the end are each connected to at most one other ring. In particular, a structure consisting of a single ring is also a chain.

Of course, a ring may be connected to three or more other rings. In such a structure, if opening and removing one ring leaves all remaining rings forming chains (or leaves no ring at all), that ring is called a critical ring. In other words, removing a critical ring leaves only chains.

Consider the seven rings numbered 0 through 6 in the figure below. This structure has two critical rings. One is ring 2: removing it leaves the three chains [1], [0, 5, 3, 4], and [6]. The other is ring 3: removing it leaves the three chains [1, 2, 0, 5], [4], and [6]. Removing any other ring leaves a part that is not a chain. For example, removing ring 5 leaves [6] as a chain, but the part made of rings 0, 1, 2, 3, and 4 is not a chain.

Your task is to count the number of critical rings in the given ring structure.

Initially there are N rings that are not connected to one another; then two kinds of operations are given in order.

  • Link(A, B) — connect ring A and ring B. A and B are different, and it is guaranteed that at this moment the two rings are not yet connected. There are no other restrictions (and no physical constraints apply). Link(A, B) and Link(B, A) mean the same operation.
  • CountCritical() — compute and output the number of critical rings in the current structure.

Input

The first line contains the number of rings N and the number of operations L. Each of the following L lines gives one operation in order. A line containing -1 is a CountCritical() call; a line containing two integers A and B is a Link(A, B) call. The rings are numbered from 0 to N − 1.

Output

Each time a CountCritical() operation is given, output its result (the number of critical rings) on its own line, in the order the operations are given.

Examples5

  1. Example 1

    Input
    7 13
-1
1 2
-1
0 5
-1
2 0
-1
3 2
-1
3 5
-1
4 3
-1
    Expected output
    7
7
7
7
4
3
2

  2. Example 2

    Input
    1 1
-1
    Expected output
    1

  3. Example 3

    Input
    2 3
-1
0 1
-1
    Expected output
    2
2

  4. Example 4

    Input
    5 8
0 1
-1
0 2
-1
0 3
-1
0 4
-1
    Expected output
    5
5
4
1

  5. Example 5

    Input
    8 14
0 1
-1
1 2
-1
2 3
-1
3 4
-1
4 5
-1
5 6
-1
6 7
-1
    Expected output
    8
8
8
8
8
8
8