# CFR 788 B. Weird journey ( Euler's Path, Ad hoc )

Problem - B - Codeforces

The first line contains two integers n, m (1 ≤ n, m ≤ 1e6) — the number of cities and roads in Uzhlyandia, respectively.
Each 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.
It 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.

O( N )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = ( int ) 1e6;

int N, M;
int deg[ MAXN ];
int vis[ MAXN ];
int sl; // self loop

int fa[ MAXN ];
int find( int x ){
return fa[ x ] == x ? x : fa[ x ] = find( fa[ x ] );
}
void unite( int x, int y ){
int a = find( x );
int b = find( y );
fa[ a ] = b;
}

signed main(){
ios::sync_with_stdio( 0 );
{
cin >> N >> M;
for( int i = 0; i < N; ++i ){
fa[ i ] = i;
}
for( int i = 0; i < M; ++i ){
int u, v;
cin >> u >> v;
--u, --v;
vis[ u ] = vis[ v ] = 1;
if( u == v ){
++sl;
} else{
++deg[ u ];
++deg[ v ];
unite( u, v );
}
}
set< int > bag;
for( int i = 0; i < N; ++i ){
if( not vis[ i ] ) continue;
bag.emplace( find( i ) );
}
if( bag.size() > 1 ){
cout << "0\n";
exit( 0 );
}
}
{
long long ans = 0LL;
int ecnt = 0;
for( int i = 0; i < N; ++i ){
ans += 1LL * deg[ i ] * ( deg[ i ] - 1 ) / 2;
ecnt += deg[ i ];
}
ecnt /= 2;
ans += 1LL * ecnt * sl;
ans += 1LL * sl * ( sl - 1 ) / 2;
cout << ans << endl;
}
return 0;
}
```