B. Weird journey

小男孩Igor想成为一名旅行者。起初，他决定访问自己祖国——Uzhlyandia的所有城市。 众所周知，Uzhlyandia有#cf_span[n]座城市，由#cf_span[m]条双向道路连接。此外，该国中不存在两条道路连接相同的两个城市，但可能存在起点和终点为同一城市的道路。Igor希望提前规划他的旅程。他认为一条路径是 _好_ 的，当且仅当该路径恰好经过#cf_span[m - 2]条道路两次，而其余#cf_span[2]条道路恰好经过一次。好的路径可以在Uzhlyandia的任意城市开始和结束。 现在他想知道Uzhlyandia中有多少条不同的好路径。两条路径被认为是不同的，当且仅当它们恰好经过一次的道路集合不同。帮助Igor——计算好路径的数量。 第一行包含两个整数#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]之间有一条道路。 保证输入中不会出现重复的道路。这也意味着每个城市最多只有一条连接自身的道路。 请输出一个整数——Uzhlyandia中好路径的数量。 在第一个样例中，好路径如下： 存在与上述相同的路径，因为它们恰好经过一次的道路集合相同： 因此，答案是#cf_span[6]。 在第二个测试用例中，Igor无法走完所有道路。 在第三个测试用例中，Igor恰好每条道路走一次。 ## Input 第一行包含两个整数#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]之间有一条道路。保证输入中不会出现重复的道路。这也意味着每个城市最多只有一条连接自身的道路。 ## Output 请输出一个整数——Uzhlyandia中好路径的数量。 [samples] ## Note 在第一个样例中，好路径如下：#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恰好每条道路走一次。

Let $ G = (V, E) $ be an undirected multigraph with $ |V| = n $, $ |E| = m $, and no duplicate edges (but self-loops allowed). A path is **good** if it traverses exactly two edges **once**, and all other $ m - 2 $ edges **exactly twice**. We are to count the number of **distinct sets of two edges** $ \{e_1, e_2\} \subseteq E $ such that there exists a walk in $ G $ that traverses $ e_1 $ and $ e_2 $ once, and every other edge twice. --- ### Key Observations: 1. **Eulerian Trail Condition (for multigraphs):** A walk that traverses each edge in a multigraph a specified number of times exists if and only if the **degree constraints** of the underlying multigraph (with multiplicities) satisfy Eulerian trail conditions. 2. **Effect of traversing edges twice:** Traversing an edge twice contributes $ 4 $ to the total degree sum (2 per endpoint), but for connectivity and parity, we consider **net parity of edge usage**. Let $ H $ be the subgraph consisting of the two edges traversed **once**. All other edges are traversed twice → they contribute even degree to each vertex, so **do not affect parity**. Therefore, the **parity of vertex degrees** in the walk is determined **only** by the two edges in $ H $. 3. **Parity constraint for existence of walk:** In any walk, all vertices except possibly two must have **even degree** in the multiset of traversed edges. The two endpoints of the walk (start and end) may have odd degree. So, for a walk to exist that uses two edges once and all others twice, the subgraph $ H $ (the two edges used once) must induce a subgraph where **exactly zero or two vertices have odd degree**. That is, the multiset of endpoints of the two edges must form a subgraph with **0 or 2 vertices of odd degree**. But each edge contributes 1 to the degree of each endpoint. So: - If the two edges are **distinct and non-loop**, then the degree parities of the four endpoints are affected. - If one or both edges are **self-loops**, they contribute 2 to the degree of one vertex → even → no parity change. So we analyze based on types of edge pairs. --- ### Case Analysis: Let $ H = \{e_1, e_2\} $ be a pair of edges (unordered, distinct). We consider the **degree parity vector** modulo 2 induced by $ H $ on the vertices. - A **self-loop** at vertex $ v $: adds 2 to deg($ v $) → even → **no parity change**. - A **non-loop edge** $ (u, v) $: adds 1 to deg($ u $) and deg($ v $) → flips parity of both. So, define: - Let $ s $ = number of self-loops in $ H $ (0, 1, or 2). - Let $ r $ = number of non-loop edges in $ H $ = $ 2 - s $. Then, the number of vertices with **odd degree** in $ H $ is equal to the number of **distinct endpoints** among the non-loop edges, **counting multiplicity modulo 2**. We need this number to be **0 or 2** for a valid walk to exist. #### Case 1: $ s = 2 $ → both edges are self-loops → Each self-loop adds even degree → total degree parities unchanged → all degrees even → **valid**. → Any pair of self-loops is valid. #### Case 2: $ s = 1 $ → one self-loop, one non-loop edge → The non-loop edge flips parity of two vertices → two vertices have odd degree → **valid**. → Any pair of one self-loop and one non-loop edge is valid. #### Case 3: $ s = 0 $ → two non-loop edges We have two edges $ e_1 = (u,v) $, $ e_2 = (x,y) $. We need the symmetric difference of their endpoints to have 0 or 2 vertices of odd degree. Let’s define the multiset of endpoints: $ \{u, v, x, y\} $. Each endpoint appears with multiplicity → degree parity = number of times it appears mod 2. Possible subcases: - **Case 3a**: The two edges are **identical** → not possible (input guarantees no duplicate edges). - **Case 3b**: The two edges are **disjoint** → 4 distinct endpoints → each appears once → 4 vertices of odd degree → **invalid**. - **Case 3c**: The two edges share **one vertex** → e.g., $ (a,b), (b,c) $ → endpoints: $ a, b, b, c $ → degrees: a:1, b:2, c:1 → odd degrees at a and c → **2 odd** → **valid**. - **Case 3d**: The two edges are the **same** → not allowed. - **Case 3e**: The two edges are **parallel** → not allowed (input says no duplicate edges). - **Case 3f**: The two edges form a **multi-edge between same pair** → not allowed. - **Case 3g**: The two edges form a **triangle**? No, just two edges. Wait — what if the two edges are the same? Not allowed. So only valid subcases for two non-loop edges: - **Shared vertex** → 2 odd-degree vertices → valid. - **Disjoint** → 4 odd-degree vertices → invalid. But what if the two edges are **identical in endpoints**? Not allowed. Also: what if the two edges are **self-loops on same vertex**? Already covered in Case 1. So for two non-loop edges: valid **iff they share exactly one vertex**. Note: if they share **two vertices** → they are the same edge → invalid. So: two distinct non-loop edges form a valid pair **iff they are adjacent** (i.e., share exactly one vertex). Also: if both edges are incident to the same two vertices? That would be a multi-edge → forbidden. So: only **adjacent edges** (sharing exactly one endpoint) are valid. Note: two edges sharing two endpoints = same edge → excluded. So: - Valid pairs of non-loop edges: pairs of edges that are **incident to a common vertex** and are **not the same edge**. This is equivalent to: for each vertex $ v $, count the number of unordered pairs of distinct edges incident to $ v $, and sum over all vertices. But: if two edges are incident to two different vertices, we might double-count? Wait: if two edges $ e_1 = (a,b) $, $ e_2 = (b,c) $, they are counted at vertex $ b $. They are not counted at $ a $ or $ c $, because $ e_1 $ and $ e_2 $ are not both incident to $ a $ or $ c $. So: each valid pair of non-loop edges that share a common vertex is counted **exactly once** — at the vertex they share. Therefore: Let $ d_v $ = degree of vertex $ v $ (counting self-loops as 1, since each self-loop contributes 1 to the edge count, even though it contributes 2 to degree). Actually: in the graph, each non-loop edge contributes 1 to the degree count of two vertices. Each self-loop contributes 1 to the edge count, and 2 to the degree, but for our purpose — we are counting **number of edges incident to vertex**, so: Define $ \deg(v) $ = number of non-loop edges incident to $ v $ + number of self-loops at $ v $. Wait: for counting **pairs of edges incident to v**, we need the total number of edges incident to $ v $, including self-loops. But: a self-loop at $ v $ is one edge incident to $ v $. So, let: - $ \deg(v) $ = total number of edges incident to $ v $, where a self-loop counts as 1 incident edge. Then, the number of unordered pairs of edges incident to $ v $ is $ \binom{\deg(v)}{2} $. But: this counts all pairs of edges incident to $ v $, including pairs where one or both are self-loops. But we already split cases. Actually, we need to separate: Let: - $ L $ = set of self-loops. Let $ \ell = |L| $. - $ E' $ = set of non-loop edges. For a pair $ \{e_1, e_2\} $ to be valid: - **Case 1**: Both in $ L $ → valid. Count: $ \binom{\ell}{2} $ - **Case 2**: One in $ L $, one in $ E' $ → valid. Count: $ \ell \cdot |E'| = \ell \cdot (m - \ell) $ - **Case 3**: Both in $ E' $ → valid iff they share a common endpoint. Now, for Case 3: number of unordered pairs of distinct non-loop edges that share a common vertex. For each vertex $ v $, let $ d_v $ = number of non-loop edges incident to $ v $. Then, number of such pairs at vertex $ v $: $ \binom{d_v}{2} $ Sum over all $ v $: $ \sum_{v=1}^n \binom{d_v}{2} $ But note: each non-loop edge $ (u,v) $ contributes to $ d_u $ and $ d_v $. So total count of such valid adjacent pairs is $ \sum_{v} \binom{d_v}{2} $ Therefore, total number of good paths is: $$ \boxed{ \binom{\ell}{2} + \ell(m - \ell) + \sum_{v=1}^n \binom{d_v}{2} } $$ Where: - $ \ell $ = number of self-loops in the graph. - $ d_v $ = number of **non-loop** edges incident to vertex $ v $. - $ m $ = total number of edges. Note: $ \sum_{v=1}^n d_v = 2(m - \ell) $, since each non-loop edge contributes to two degrees. This formula gives the number of unordered pairs $ \{e_1, e_2\} $ of edges such that the walk traversing $ e_1, e_2 $ once and others twice exists. And since the problem says: **Two paths are considered different if the sets of roads the paths go over exactly once differ**, we are counting **sets** of two edges, so unordered pairs. Thus, the answer is: $$ \boxed{ \binom{\ell}{2} + \ell(m - \ell) + \sum_{v=1}^{n} \binom{d_v}{2} } $$ Where: - $ \ell = $ number of self-loops, - $ d_v = $ number of non-loop edges incident to vertex $ v $, - $ m = $ total number of edges. We can compute this in $ O(n + m) $ time. --- ### Final Answer: $$ \boxed{\binom{\ell}{2} + \ell(m - \ell) + \sum_{v=1}^{n} \binom{d_v}{2}} $$