Unique path - MarisaOJ: Marisa Online Judge

Unique path

Time limit: 1000 ms
Memory limit: 256 MB
Given a connected graph $G$ with $n$ vertices and $m$ undirected edges. Count the number of pairs $u, v$ with $u < v$ such that there exists exactly one path from $u$ to $v$. A path is considered valid if each edge and vertex on the path is traversed exactly once. ### Input - The first line contains two positive integers $n, m$. - The next $m$ lines, each containing two positive integers $u_i, v_i$ that describe an edge of the graph. ### Output - Print the answer to the problem. ### Constraints - $1 \le n,m \le 222222.$ ### Example Input ``` 5 5 1 2 1 5 3 2 4 5 1 3 ``` Output ``` 3 ```