English · Original
Chinese · Translation
Formal · Original
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.
<center> There are $6$ connected components, $2$ of them are cycles: $[7, 10, 16]$ and $[5, 11, 9, 15]$.</center>
## Input
The first line contains two integer numbers $n$ and $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m \le 2 \cdot 10^5$) — number of vertices and edges.
The following $m$ lines contains edges: edge $i$ is given as a pair of vertices $v_i$, $u_i$ ($1 \le v_i, u_i \le n$, $u_i \ne v_i$). There is no multiple edges in the given graph, i.e. for each pair ($v_i, u_i$) there no other pairs ($v_i, u_i$) and ($u_i, v_i$) in the list of edges.
## Output
Print one integer — the number of connected components which are also cycles.
[samples]
## Note
In the first example only component $[3, 4, 5]$ is also a cycle.
The illustration above corresponds to the second example.
你被给定一个包含 $n$ 个顶点和 $m$ 条边的无向图。你的任务是找出有多少个连通分量是环。
以下是图论的一些定义。
一个无向图由两个集合组成：顶点集合和边集合。每条边连接一对顶点。所有边都是双向的（即如果顶点 $a$ 与顶点 $b$ 相连，则顶点 $b$ 也与顶点 $a$ 相连）。边不能连接顶点与自身，一对顶点之间最多只有一条边。
两个顶点 $u$ 和 $v$ 属于同一个连通分量，当且仅当存在至少一条沿边连接 $u$ 和 $v$ 的路径。
一个连通分量是环，当且仅当它的顶点可以重新排列，使得：
环中不包含除上述之外的其他边。根据定义，任何环都包含三个或更多顶点。
第一行包含两个整数 $n$ 和 $m$（$1 lt.eq n lt.eq 2 dot.op 10^5$，$0 lt.eq m lt.eq 2 dot.op 10^5$）——分别表示顶点数和边数。
接下来的 $m$ 行每行给出一条边：第 $i$ 条边由一对顶点 $v_i$、$u_i$ 给出（$1 lt.eq v_i, u_i lt.eq n$，$u_i != v_i$）。给定图中不存在重边，即对于每对 $(v_i, u_i)$，在边列表中不存在其他对 $(v_i, u_i)$ 或 $(u_i, v_i)$。
请输出一个整数——既是环的连通分量的数量。
在第一个例子中，只有分量 $[ 3, 4, 5 ]$ 是一个环。
上述图示对应第二个例子。
## Input
第一行包含两个整数 $n$ 和 $m$（$1 lt.eq n lt.eq 2 dot.op 10^5$，$0 lt.eq m lt.eq 2 dot.op 10^5$）——分别表示顶点数和边数。接下来的 $m$ 行每行给出一条边：第 $i$ 条边由一对顶点 $v_i$、$u_i$ 给出（$1 lt.eq v_i, u_i lt.eq n$，$u_i != v_i$）。给定图中不存在重边，即对于每对 $(v_i, u_i)$，在边列表中不存在其他对 $(v_i, u_i)$ 或 $(u_i, v_i)$。
## Output
请输出一个整数——既是环的连通分量的数量。
[samples]
## Note
在第一个例子中，只有分量 $[ 3, 4, 5 ]$ 是一个环。上述图示对应第二个例子。
**Definitions**
Let $ G = (V, E) $ be an undirected graph with:
- $ V $: set of vertices, $ |V| = n $
- $ E $: set of edges, $ |E| = m $
A **connected component** is a maximal connected subgraph of $ G $.
A connected component $ C = (V_C, E_C) $ is a **cycle** if and only if:
- $ |V_C| \geq 3 $,
- Every vertex in $ V_C $ has degree 2 in $ C $,
- $ |E_C| = |V_C| $.
**Constraints**
1. $ 1 \leq n \leq 2 \cdot 10^5 $
2. $ 0 \leq m \leq 2 \cdot 10^5 $
3. No self-loops or multiple edges.
**Objective**
Compute the number of connected components $ C $ of $ G $ such that $ C $ is a cycle.
API Response (JSON)
{
"problem": {
"name": "E. Cyclic Components",
"description": {
"content": "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 un",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF977E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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.\n\nHere are some definitions of graph theory.\n\nAn un...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "你被给定一个包含 $n$ 个顶点和 $m$ 条边的无向图。你的任务是找出有多少个连通分量是环。\n\n以下是图论的一些定义。\n\n一个无向图由两个集合组成：顶点集合和边集合。每条边连接一对顶点。所有边都是双向的（即如果顶点 $a$ 与顶点 $b$ 相连，则顶点 $b$ 也与顶点 $a$ 相连）。边不能连接顶点与自身，一对顶点之间最多只有一条边。\n\n两个顶点 $u$ 和 $v$ 属于同一个连通分量，当且仅...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ G = (V, E) $ be an undirected graph with: \n- $ V $: set of vertices, $ |V| = n $ \n- $ E $: set of edges, $ |E| = m $ \n\nA **connected component** is a maximal connected subgr...",
"is_translate": false,
"language": "Formal"
}
]
}