Number of Vertex Cactus Components

Time limit2sMemory limit128 MB

Summary
Given a graph, count connected components that are vertex cacti, meaning every vertex lies in at most one simple cycle.
Level

Medium7 of 10

Topics
Graph, DFS, Union-find
Solved
No attempts yet

Problem

A vertex cactus is a connected undirected graph with the following property.

  • Each vertex belongs to at most one simple cycle.

A simple cycle is a cycle in which every vertex, except for the repeated start/end vertex, appears at most once.

The following picture shows a vertex cactus.

You are given an undirected graph G with N vertices numbered from 1 to N, together with all of its edges. Count how many connected components of G are vertex cacti.

A connected component is a set of vertices such that every pair of vertices in the set is connected by a path, and no vertex in the set is connected to any vertex outside the set.

Input

The first line contains two integers N and M, the number of vertices and edges in G. N is a positive integer not greater than 200, and M is a nonnegative integer.

Each of the next M lines contains two space-separated integers describing one edge. No edge is repeated, and every pair of vertices is connected by at most one edge.

Output

Print one integer: the number of connected components of G that are vertex cacti.

Examples4

  1. Example 1

    Input
    3 3
1 2
1 3
2 3
    Expected output
    1

  2. Example 2

    Input
    10 0
    Expected output
    10

  3. Example 3

    Input
    5 3
1 2
3 4
4 5
    Expected output
    2

  4. Example 4

    Input
    17 19
1 2
2 3
3 4
4 5
5 3
1 3
6 7
7 8
6 8
8 9
9 10
10 11
11 9
12 13
14 15
15 16
16 17
14 17
14 16
    Expected output
    2