## Algorithm

E. Cyclic Components
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an undirected graph consisting of n vertices and m edges. Your task is to find the number of connected components which are cycles.

Here are some definitions of graph theory.

An undirected graph consists of two sets: set of nodes (called vertices) and set of edges. Each edge connects a pair of vertices. All edges are bidirectional (i.e. if a vertex a is connected with a vertex b, a vertex b is also connected with a vertex a). An edge can't connect vertex with itself, there is at most one edge between a pair of vertices.

Two vertices u and v belong to the same connected component if and only if there is at least one path along edges connecting u and v.

A connected component is a cycle if and only if its vertices can be reordered in such a way that:

• the first vertex is connected with the second vertex by an edge,
• the second vertex is connected with the third vertex by an edge,
• ...
• the last vertex is connected with the first vertex by an edge,
• all the described edges of a cycle are distinct.

A cycle doesn't contain any other edges except described above. By definition any cycle contains three or more vertices.

There are 66 connected components, 22 of them are cycles: [7,10,16][7,10,16] and [5,11,9,15][5,11,9,15].
Input

The first line contains two integer numbers n and m (1n21051≤�≤2⋅1050m21050≤�≤2⋅105) — number of vertices and edges.

The following m lines contains edges: edge i is given as a pair of vertices vi��ui�� (1vi,uin1≤��,��≤�uivi��≠��). There is no multiple edges in the given graph, i.e. for each pair (vi,ui��,��) there no other pairs (vi,ui��,��) and (ui,vi��,��) in the list of edges.

Output

Print one integer — the number of connected components which are also cycles.

Examples
input
Copy
5 41 23 45 43 5
output
Copy
1
input
Copy
17 151 81 125 1111 99 1515 54 133 134 310 167 1016 714 314 417 6
output
Copy
2
Note

In the first example only component [3,4,5][3,4,5] is also a cycle.

The illustration above corresponds to the second example.

## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 2e5 + 1;
int n, m, res;
bool vis[N];
vector<vector<int> > g;
vector<int> all;

void DFS(int u) {
vis[u] = true;
all.push_back(u);

for(int i = 0;i < g[u].size(); ++i)
if(!vis[g[u][i]])
DFS(g[u][i]);
}

int main() {
cin >> n >> m;
g.resize(n);
for(int i = 0, a, b; i < m; ++i) {
cin >> a >> b;
--a, --b;
g[a].push_back(b);
swap(a, b);
g[a].push_back(b);
}

for(int i = 0; i < n; ++i) {
if(!vis[i]) {
all.clear();
DFS(i);

bool ok = true;
for(int j = 0; j < all.size(); ++j)
if(g[all[j]].size() != 2) {
ok = false;
break;
}

res += (ok && all.size() > 2);
}
}

cout << res << endl;

return 0;
}
Copy The Code &

Input

cmd
5 4
1 2
3 4
5 4
3 5

Output

cmd
1