## Editorial for Thành phố trọng yếu

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

const fi='';
maxn=20010;
maxm=200010;
var m,n,dem,s,sm:longint;
a:array[1..maxm*2] of longint;
sl,cur,pos,num,low,cha,d,mien:array[1..maxn] of longint;
b:array[1..maxm,0..1] of longint;
free:array[1..maxn] of boolean;
re:real;

procedure rf;
var i:longint;
begin
for i:=1 to m do
begin
inc(sl[b[i,0]]); inc(sl[b[i,1]]);
end;
pos[1]:=1; cur[1]:=1;
for i:=2 to n+1 do
begin
pos[i]:=pos[i-1]+sl[i-1]; cur[i]:=pos[i];
end;
for i:=1 to m do
begin
a[cur[b[i,0]]]:=b[i,1];
inc(cur[b[i,0]]);
a[cur[b[i,1]]]:=b[i,0];
inc(cur[b[i,1]]);
end;
end;

function min(u,v:longint):longint;
begin
if u<v then min:=u else min:=v;
end;

procedure visit(x,y:longint;var s:longint);
var i,t,nm,sum,sq,u:longint;
begin
inc(dem); num[x]:=dem; low[x]:=n+1;
s:=0; nm:=0; sum:=0; sq:=0;t:=0; u:=0;
for i:=pos[x] to pos[x+1]-1 do
if a[i]<>y then
begin
if cha[a[i]]<>0 then low[x]:=min(low[x],num[a[i]])
else
begin
cha[a[i]]:=x;
visit(a[i],x,t);
low[x]:=min(low[x],low[a[i]]);
s:=s+t;
if low[a[i]]>=num[x] then
begin
sum:=sum+t;
sq:=sq+t*t;
end else u:=u+t;
end;
end;
s:=s+1;
t:=mien[d[x]]-s+u;
sum:=sum+t;
sq:=sq+t*t;
re:=re+(sum*sum-sq) div 2;
end;

procedure dfs(x,y:longint);
var i:longint;
begin
d[x]:=sm; inc(mien[sm]); free[x]:=true;
for i:=pos[x] to pos[x+1]-1 do
if not free[a[i]] and (a[i]<>y) then dfs(a[i],x);
end;

procedure pr;
var i,j:longint;
begin
dem:=0; sm:=0;
for i:=1 to n do
if not free[i] then
begin
inc(sm);
dfs(i,0);
end;
for i:=1 to n do
if num[i]=0 then
begin
cha[i]:=-1;
visit(i,0,s);
end;
writeln(re/n:0:2);
end;

begin
assign(input,fi); reset(input);
rf;
pr;
close(input);
end.


#### Code mẫu của happyboy99x

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;

#define TR(v,i) for(typeof((v).begin()) i=(v).begin();i!=(v).end();++i)
const int N = 20000 + 5, INF = 1000000000;
vector<vector<int> > g;
int n, m, d[N], low[N], r[N], timed;
bool vst[N];

void enter() {
scanf("%d%d",&n,&m); g.resize(n);
for(int i = 0; i < m; ++i) {
int u, v; scanf("%d%d",&u,&v);
g[--u].push_back(--v);
g[v].push_back(u);
}
}

int sqr(const int &x) { return x * x; }
long long res;

void dfs(int u, int p, int nnode) {
d[u] = ++timed; r[u] = 1; low[u] = INF;
int rem = nnode - 1, add = sqr(nnode - 1), nchild = 0;
TR(g[u], it) {
int v = *it;
if(d[v]) { if(v != p) low[u] = min(low[u], d[v]); }
else {
dfs(v, u, nnode); low[u] = min(low[u], low[v]);
r[u] += r[v]; ++nchild;
if((p == -1 && nchild > 1 || p != -1) && low[v] >= d[u])
rem -= r[v], add -= sqr(r[v]);
}
}
if(p == -1 && nchild > 1) rem -= r[g[u][0]], add -= sqr(r[g[u][0]]);
}

int bfs(int u) {
int res = 0; queue<int> q; q.push(u); vst[u] = 1;
while(!q.empty()) {
int u = q.front(); q.pop(); ++res;
TR(g[u], v) if(vst[*v] == 0) vst[*v] = 1, q.push(*v);
}
return res;
}

void solve() {
for(int u = 0; u < n; ++u) if(vst[u] == 0) dfs(u, -1, bfs(u));
printf("%.2lf\n", (double) res / (2*n));
}

int main() {
enter();
solve();
return 0;
}


#include <bits/stdc++.h>

using namespace std;

const int N = 200005;

int n, m, cc;
int Time;
int was[N];
int par[N];
int root[N];
int num[N], low[N];
int Size[N];
long long ans[N];
vector<int> a[N];

void dfs(int u) {
was[u] = cc; num[u] = ++Time; low[u] = N; Size[u] = 1;
for (int v : a[u]) if (v != par[u]) {
if (was[v]) {
low[u] = min(low[u], num[v]);
} else {
par[v] = u;
dfs(v);
low[u] = min(low[u], low[v]);
Size[u] += Size[v];
}
}
}

int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v; cin >> u >> v;
a[u].push_back(v); a[v].push_back(u);
}
for (int u = 1; u <= n; ++u) {
sort(a[u].begin(), a[u].end());
a[u].resize(unique(a[u].begin(), a[u].end()) - a[u].begin());
}
for (int i = 1; i <= n; ++i) if (!was[i]) {
++cc;
root[cc] = i;
dfs(i);
}
for (int u = 1; u <= n; ++u) {
long long cur = 0, sizePar = Size[root[was[u]]] - 1;
for (int v : a[u]) if (par[v] == u && low[v] >= num[u]) {
ans[u] += cur * Size[v];
cur += Size[v];
sizePar -= Size[v];
}
if (sizePar) {
ans[u] += cur * sizePar;
}
}
long long sum = 0;
for (int u = 1; u <= n; ++u) sum += ans[u];
cout << setprecision(2) << fixed << (long double)sum / n << endl;
return 0;
}


#### Code mẫu của RR

uses math;
const
MAXN=20111;

type
list=^node;
node=record
u:longint;
next:list;
end;

var
p:list;
begin
new(p); p^.u:=u;
p^.next:=a; a:=p;
end;

var
n,m,u,v,cnt,sl:longint;
ke:array[1..MAXN] of list;
res:int64;
w,low,num,reg,father,count:array[1..MAXN] of longint;

procedure dfs1(u:longint);
var
v:longint;
p:list;
begin
reg[u]:=sl; w[u]:=1;

inc(cnt);
low[u]:=cnt; num[u]:=cnt;

p:=ke[u];
while p<>nil do
begin
v:=p^.u; p:=p^.next;
if v=father[u] then continue;

if num[v]=0 then
begin
father[v]:=u;
dfs1(v);
low[u]:=min(low[u],low[v]);
inc(w[u],w[v]);
end
else low[u]:=min(low[u],num[v]);
end;
end;

procedure dfs2(u:longint);
var
v,tmp:longint;
p:list;
begin
p:=ke[u]; tmp:=count[reg[u]]-1;
while p<>nil do
begin
v:=p^.u; p:=p^.next;
if father[v]<>u then continue;
dfs2(v);

//Cac dinh thuoc cay con goc v khong di duoc len tren dinh u
if low[v]>=num[u] then
begin
tmp:=tmp-w[v];
res:=res+int64(w[v])*tmp;
end;
end;
end;

begin
for m:=1 to m do
begin
end;

sl:=0;
for u:=1 to n do
if num[u]=0 then
begin
cnt:=0;
inc(sl);
dfs1(u);
end;

for u:=1 to n do
inc(count[reg[u]]);

for u:=1 to n do
if father[u]=0 then
dfs2(u);

writeln(res/n:0:2);
end.


#### Code mẫu của skyvn97

#include<cstdio>
#include<iostream>
#include<queue>
#include<vector>
#define MAX   20020
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
using namespace std;
typedef long long ll;
vector<int> g[MAX];
int low[MAX];
int num[MAX];
int ncp[MAX];
int nc[MAX];
int sz[MAX];
int n,m,cnt;
ll sp;
void minimize(int &x,const int &y) {
if (x>y) x=y;
}
scanf("%d",&n);
scanf("%d",&m);
REP(i,m) {
int u,v;
scanf("%d",&u);
scanf("%d",&v);
g[u].push_back(v);
g[v].push_back(u);
}
}
ll sumproduct(const vector<int> &v) {
int sumall=0;
ll sumsqr=0LL;
FORE(it,v) {
sumall+=*it;
sumsqr+=1LL*(*it)*(*it);
}
return (1LL*sumall*sumall-sumsqr)/2;
}
int BFS(int s,int id) {
queue<int> q;
while (!q.empty()) q.pop();
ncp[s]=id;
q.push(s);
int ret=1;
while (!q.empty()) {
int u=q.front();q.pop();
FORE(it,g[u]) if (ncp[*it]==0) {
ncp[*it]=id;
q.push(*it);
ret++;
}
}
return (ret);
}
void visit(int u) {
vector<int> nchild=vector<int>();
int nrest=0;
cnt++;
low[u]=n+7;
num[u]=cnt;
FORE(it,g[u]) {
int v=*it;
if (num[v]==0) {
visit(v);
nc[u]+=nc[v];
if (low[v]>=num[u]) nchild.push_back(nc[v]);
else nrest+=nc[v];
minimize(low[u],low[v]);
}
else minimize(low[u],num[v]);
}
nc[u]++;
nrest+=sz[ncp[u]]-nc[u];
nchild.push_back(nrest);
sp+=sumproduct(nchild);
}
void process(void) {
int tmp=0;
FOR(i,1,n) if (ncp[i]==0) {
tmp++;
sz[tmp]=BFS(i,tmp);
}
FOR(i,1,n) if (num[i]==0) visit(i);
printf("%.2lf",1.0*sp/n);
}
int main(void) {