{"problem":{"name":"D. Weird journey","description":{"content":"Little boy Igor wants to become a traveller. At first, he decided to visit all the cities of his motherland — Uzhlyandia. It is widely known that Uzhlyandia has _n_ cities connected with _m_ bidirect","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF789D"},"statements":[{"statement_type":"Markdown","content":"Little boy Igor wants to become a traveller. At first, he decided to visit all the cities of his motherland — Uzhlyandia.\n\nIt is widely known that Uzhlyandia has _n_ cities connected with _m_ bidirectional roads. Also, there are no two roads in the country that connect the same pair of cities, but roads starting and ending in the same city can exist. Igor wants to plan his journey beforehand. Boy thinks a path is _good_ if the path goes over _m_ - 2 roads twice, and over the other 2 exactly once. The good path can start and finish in any city of Uzhlyandia.\n\nNow he wants to know how many different good paths are in Uzhlyandia. Two paths are considered different if the sets of roads the paths goes over exactly once differ. Help Igor — calculate the number of good paths.\n\n## Input\n\nThe first line contains two integers _n_, _m_ (1 ≤ _n_, _m_ ≤ 106) — the number of cities and roads in Uzhlyandia, respectively.\n\nEach of the next _m_ lines contains two integers _u_ and _v_ (1 ≤ _u_, _v_ ≤ _n_) that mean that there is road between cities _u_ and _v_.\n\nIt is guaranteed that no road will be given in the input twice. That also means that for every city there is no more than one road that connects the city to itself.\n\n## Output\n\nPrint out the only integer — the number of good paths in Uzhlyandia.\n\n[samples]\n\n## Note\n\nIn first sample test case the good paths are:\n\n*   2 → 1 → 3 → 1 → 4 → 1 → 5,\n*   2 → 1 → 3 → 1 → 5 → 1 → 4,\n*   2 → 1 → 4 → 1 → 5 → 1 → 3,\n*   3 → 1 → 2 → 1 → 4 → 1 → 5,\n*   3 → 1 → 2 → 1 → 5 → 1 → 4,\n*   4 → 1 → 2 → 1 → 3 → 1 → 5.\n\nThere are good paths that are same with displayed above, because the sets of roads they pass over once are same:\n\n*   2 → 1 → 4 → 1 → 3 → 1 → 5,\n*   2 → 1 → 5 → 1 → 3 → 1 → 4,\n*   2 → 1 → 5 → 1 → 4 → 1 → 3,\n*   3 → 1 → 4 → 1 → 2 → 1 → 5,\n*   3 → 1 → 5 → 1 → 2 → 1 → 4,\n*   4 → 1 → 3 → 1 → 2 → 1 → 5,\n*   and all the paths in the other direction.\n\nThus, the answer is 6.\n\nIn the second test case, Igor simply can not walk by all the roads.\n\nIn the third case, Igor walks once over every road.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"小男孩Igor想成为一名旅行者。起初，他决定访问他祖国Uzhlyandia的所有城市。\n\n众所周知，Uzhlyandia有#cf_span[n]座城市，由#cf_span[m]条双向道路连接。此外，该国中不存在连接同一对城市的两条道路，但可能存在起点和终点为同一城市的道路。Igor希望提前规划他的行程。他认为一条路径是_好的_，当且仅当该路径经过#cf_span[m - 2]条道路恰好两次，而经过其余#cf_span[2]条道路恰好一次。好的路径可以在Uzhlyandia的任意城市开始和结束。\n\n现在他想知道Uzhlyandia中有多少条不同的好路径。两条路径被认为是不同的，当且仅当它们恰好经过一次的道路集合不同。帮助Igor——计算好路径的数量。\n\n第一行包含两个整数#cf_span[n], #cf_span[m] #cf_span[(1 ≤ n, m ≤ 10^6)]——分别是Uzhlyandia的城市数和道路数。\n\n接下来的#cf_span[m]行，每行包含两个整数#cf_span[u]和#cf_span[v]（#cf_span[1 ≤ u, v ≤ n]），表示城市#cf_span[u]和#cf_span[v]之间有一条道路。\n\n保证输入中不会出现重复的道路。这也意味着每个城市最多只有一条连接自身的道路。\n\n请输出一个整数——Uzhlyandia中好路径的数量。\n\n在第一个样例中，好路径为：\n\n存在与上述相同的路径，因为它们恰好经过一次的道路集合相同：\n\n因此，答案是#cf_span[6]。\n\n在第二个测试用例中，Igor无法走完所有道路。\n\n在第三个测试用例中，Igor恰好经过每条道路一次。\n\n## Input\n\n第一行包含两个整数#cf_span[n], #cf_span[m] #cf_span[(1 ≤ n, m ≤ 10^6)]——分别是Uzhlyandia的城市数和道路数。接下来的#cf_span[m]行，每行包含两个整数#cf_span[u]和#cf_span[v]（#cf_span[1 ≤ u, v ≤ n]），表示城市#cf_span[u]和#cf_span[v]之间有一条道路。保证输入中不会出现重复的道路。这也意味着每个城市最多只有一条连接自身的道路。\n\n## Output\n\n请输出一个整数——Uzhlyandia中好路径的数量。\n\n[samples]\n\n## Note\n\n在第一个样例中，好路径为：#cf_span[2 → 1 → 3 → 1 → 4 → 1 → 5]，#cf_span[2 → 1 → 3 → 1 → 5 → 1 → 4]，#cf_span[2 → 1 → 4 → 1 → 5 → 1 → 3]，#cf_span[3 → 1 → 2 → 1 → 4 → 1 → 5]，#cf_span[3 → 1 → 2 → 1 → 5 → 1 → 4]，#cf_span[4 → 1 → 2 → 1 → 3 → 1 → 5]。存在与上述相同的路径，因为它们恰好经过一次的道路集合相同：#cf_span[2 → 1 → 4 → 1 → 3 → 1 → 5]，#cf_span[2 → 1 → 5 → 1 → 3 → 1 → 4]，#cf_span[2 → 1 → 5 → 1 → 4 → 1 → 3]，#cf_span[3 → 1 → 4 → 1 → 2 → 1 → 5]，#cf_span[3 → 1 → 5 → 1 → 2 → 1 → 4]，#cf_span[4 → 1 → 3 → 1 → 2 → 1 → 5]，以及所有反向路径。因此，答案是#cf_span[6]。在第二个测试用例中，Igor无法走完所有道路。在第三个测试用例中，Igor恰好经过每条道路一次。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**\n\n1.  Let $G = (V, E)$ be an undirected graph where $V = \\{1, \\dots, n\\}$ and $|E| = m$.\n2.  The edge set $E$ may contain self-loops $(u, u)$ but contains no multiple edges between distinct pairs of vertices.\n3.  Let $E_{loop} = \\{ (u, v) \\in E \\mid u = v \\}$ be the set of self-loops.\n4.  Let $E_{path} = \\{ (u, v) \\in E \\mid u \\neq v \\}$ be the set of edges connecting distinct vertices.\n5.  For any vertex $v \\in V$, let $\\deg_{path}(v)$ denote the number of edges in $E_{path}$ incident to $v$.\n6.  Let $G'$ be the subgraph of $G$ induced by the set of all edges $E$. $G'$ contains all vertices incident to at least one edge in $E$.\n\n**Objective**\n\nCalculate the number of pairs of distinct edges $\\{e_1, e_2\\} \\subseteq E$ such that there exists a path in $G$ traversing $e_1$ and $e_2$ exactly once each, and traversing every other edge in $E \\setminus \\{e_1, e_2\\}$ exactly twice.\n\n**Calculation**\n\nLet $N$ be the number of such pairs.\n\n1.  **Connectivity Constraint:**\n    If the subgraph $G'$ has more than 1 connected component, then:\n    $$N = 0$$\n\n2.  **Counting Formula:**\n    If $G'$ is connected (i.e., has exactly 1 connected component), then $N$ is given by:\n    $$N = \\binom{|E_{loop}|}{2} + |E_{loop}| \\cdot |E_{path}| + \\sum_{v \\in V} \\binom{\\deg_{path}(v)}{2}$$\n\n    Where $\\binom{k}{2} = \\frac{k(k-1)}{2}$ for $k \\ge 2$, and $0$ otherwise.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF789D","tags":["constructive algorithms","graphs"],"sample_group":[["5 4\n1 2\n1 3\n1 4\n1 5","6"],["5 3\n1 2\n2 3\n4 5","0"],["2 2\n1 1\n1 2","1"]],"created_at":"2026-03-03 11:00:39"}}