## Editorial for VM 10 Bài 01 - Điều kiện thời tiết

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='';
fo='';
maxn=110;
var n,m,last,sm,dem,re:longint;
a,e:array[1..maxn,1..maxn] of boolean;
b:array[1..maxn,1..maxn] of longint;
free:array[1..maxn] of boolean;
d,sl,low,num,st,dau,q:array[1..maxn] of longint;

procedure rf;
var i,x,y:longint;
begin
assign(input,fi); reset(input);
for i:=1 to m do
begin
a[x,y]:=true;
a[y,x]:=true;
end;
close(input);
end;

function pop:longint;
begin
pop:=st[last];
dec(last);
end;

procedure push(i:longint);
begin
inc(last);
st[last]:=i;
end;

function min(x,y:longint):longint;
begin
if x<y then min:=x else min:=y;
end;

procedure visit(x,y:longint);
var i:longint;
begin
inc(dem); num[x]:=dem; low[x]:=dem;
push(x);
for i:=1 to n do
if free[i] and a[x,i] and (i<>y) then
begin
if num[i]>0 then low[x]:=min(num[i],low[x])
else
begin
visit(i,x);
low[x]:=min(low[x],low[i]);
end;
end;
if num[x]=low[x] then
begin
inc(sm);
repeat
i:=pop;
free[i]:=false;
d[i]:=sm;
until i=x;
d[x]:=sm;
end;
end;

procedure pr;
var i,j,k,l,high:longint;
begin
last:=0; sm:=0; dem:=0;
for i:=1 to n do free[i]:=true;
for i:=1 to n do
if free[i] then visit(i,0);
for i:=1 to n do
begin
inc(sl[d[i]]);
b[d[i],sl[d[i]]]:=i;
end;
re:=0;
for i:=1 to n-1 do
for j:=i+1 to n do
if a[i,j] then
begin
e[d[i],d[j]]:=true;
e[d[j],d[i]]:=true;
end;
for i:=1 to n-1 do
for j:=i+1 to n do
begin
fillchar(dau,sizeof(dau),0);
dau[d[i]]:=1; high:=1; q[1]:=d[i]; l:=1;
repeat
for k:=1 to sm do
if (dau[k]=0) and e[q[l],k] then
begin
inc(high);
q[high]:=k;
dau[k]:=dau[q[l]]+1;
end;
inc(l);
until (l>high) or (dau[d[j]]>0);
if dau[d[j]]>0 then re:=re+dau[d[j]]-1;
end;
end;

procedure wf;
begin
assign(output,fo); rewrite(output);
writeln(re);
close(output);
end;

begin
rf;
pr;
wf;
end.


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

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long LL;

#define sz(a) (int((a).size()))
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 105

int n, m;
vvi g; vii e;
int qu[N], lq, hq;
bool vst[N];

int bfs(int U, int V) {
lq = 0; hq = 1; qu[0] = 0; memset(vst, 0, sizeof vst); vst[0] = 1;
int res = 0;
while(lq != hq) {
int u = qu[lq++]; ++res;
tr(g[u], it) {
if(!vst[*it] && !(u == U && V == *it || U == *it && V == u)) {
vst[*it] = 1;
qu[hq++] = *it;
}
}
}
return res;
}

int main() {
#ifndef ONLINE_JUDGE
freopen( "input.txt", "r", stdin );
//freopen( "output.txt", "w", stdout );
#endif
scanf("%d%d",&n,&m); g.resize(n);
rep(i,m) {
int u, v; scanf("%d%d",&u,&v);
g[--u].pb(--v); g[v].pb(u);
e.pb(ii(u,v));
}
LL res = 0;
tr(e, it) {
LL t = (LL) bfs(it->fi, it->se);
res += t * (n-t);
}
printf("%lld\n", res);
return 0;
}


#include <bits/stdc++.h>

using namespace std;

const int N = 1000;

int par[N];
int size[N];
vector<int> a[N];

int low[N], num[N];

int n, m;
int Time;

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

int main() {
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);
}
dfs(1);
int ans = 0;
for (int v = 2; v <= n; ++v) {
if (low[v] >= num[v])
ans += size[v] * (n - size[v]);
}
cout << ans << endl;
return 0;
}


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

#include <iostream>
#include <algorithm>
#include <vector>

#define FOR(i,a,b)  for(int i=a; i<=b; i++)
#define FORD(i,a,b) for(int i=a; i>=b; i--)
#define FORV(i,v)   for(typeof(v.begin()) i=v.begin(); i!=v.end(); i++)
#define V vector<int>
#define _ [111]
using namespace std;

int n,m,res=0,now=0;
int low _, num _, father _, weight _;
V ke _;

void inp() {
scanf("%d %d",&n,&m);
FOR(i,1,m) {
int u,v;
scanf("%d %d",&u,&v);
ke[u].push_back(v);
ke[v].push_back(u);
}
}

void dfs(int u) {
now++; num[u]=now; low[u]=now;
weight[u]=1;
FORV(v,ke[u]) {
if (*v==father[u]) continue;
if (!father[*v]) {
father[*v]=u;
dfs(*v);
weight[u]+=weight[*v];
low[u]=min(low[u],low[*v]);
}
else low[u]=min(low[u],num[*v]);
}
}

void solve() {
father[1]=1; dfs(1);

FOR(v,2,n) {
int u=father[v];
if (low[v]>num[u]) {
//            cout<<u<<" "<<v<<" "<<weight[v]<<endl;
res+=weight[v]*(n-weight[v]);
}
}
cout<<res;
}

int main() {
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
inp();
solve();
return 0;
}


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

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(int i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(int i = (a); i >= (b); --i)
#define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))

template<class F, class T> T convert(F a, int p = -1) {
stringstream ss;
if (p >= 0)
ss << fixed << setprecision(p);
ss << a;
T r;
ss >> r;
return r;
}
template<class T> T gcd(T a, T b) {
T r;
while (b != 0) {
r = a % b;
a = b;
b = r;
}
return a;
}
template<class T> T lcm(T a, T b) {
return a / gcd(a, b) * b;
}
template<class T> T sqr(T x) {
return x * x;
}
template<class T> T cube(T x) {
return x * x * x;
}
template<class T> int getbit(T s, int i) {
return (s >> i) & 1;
}
template<class T> T onbit(T s, int i) {
return s | (T(1) << i);
}
template<class T> T offbit(T s, int i) {
return s & (~(T(1) << i));
}
template<class T> int cntbit(T s) {
return s == 0 ? 0 : cntbit(s >> 1) + (s & 1);
}

const int bfsz = 1 << 16;
char bf[bfsz + 5];
int rsz = 0;
int ptr = 0;
char gc() {
if (rsz <= 0) {
ptr = 0;
rsz = (int) fread(bf, 1, bfsz, stdin);
if (rsz <= 0)
return EOF;
}
--rsz;
return bf[ptr++];
}
void ga(char &c) {
c = EOF;
while (!isalpha(c))
c = gc();
}
int gs(char s[]) {
int l = 0;
char c = gc();
while (isspace(c))
c = gc();
while (c != EOF && !isspace(c)) {
s[l++] = c;
c = gc();
}
s[l] = '\0';
return l;
}
template<class T> bool gi(T &v) {
v = 0;
char c = gc();
while (c != EOF && c != '-' && !isdigit(c))
c = gc();
if (c == EOF)
return false;
bool neg = c == '-';
if (neg)
c = gc();
while (isdigit(c)) {
v = v * 10 + c - '0';
c = gc();
}
if (neg)
v = -v;
return true;
}

typedef pair<int, int> II;
const ld PI = acos(-1.0);
const ld eps = 1e-9;
const int dr[] = { -1, 0, +1, 0};
const int dc[] = { 0, +1, 0, -1};
const int inf = (int) 1e9 + 5;
const ll linf = (ll) 1e16 + 5;
const int mod = (ll) (1e9 + eps);
#define ok puts("ok")
#define maxn 105
#define maxe 20005

int last[maxn], adj[maxe], next[maxe], E = 0, flag[maxn], run, f[maxn], vt[maxn];
int n, m, res;

adj[E] = v; next[E] = last[u]; last[u] = E++;
adj[E] = u; next[E] = last[v]; last[v] = E++;
}

int cal(int par, int u){
if(flag[u]) return 0;
flag[u] = 1;
int ret = 1;
for(int e = last[u]; e != -1; e = next[e]){
if(v == par) continue;
ret += cal(u, v);
}
return ret;
}

void go(int par, int u){
f[u] = run;
vt[u] = run++;

for(int e = last[u]; e != -1; e = next[e]){
if(v == par) continue;
if(vt[v] > -1) f[u] = min(f[u], vt[v]);
else{
go(u, v);
f[u] = min(f[u], f[v]);
if(f[v] > vt[u]){
ms(flag, 0);
int num = cal(u, v);
res += num * (n - num);
}
}
}

}

int main(){
//  freopen("in.txt", "r", stdin);

cin >> n >> m;
int u, v;
ms(last, -1);
Rep(mi, m){
scanf("%d %d", &u, &v);
}

ms(f, -1); ms(vt, -1);
res = 0;
go(0, 1);
run = 0;
cout << res;

return 0;
}


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

//#pragma comment(linker, "/STACK:16777216")
#include <algorithm>
#include <bitset>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <stack>
#include <queue>
#include <vector>
#include <utility>
using namespace std;

int n,m;
int low[105],num[105],sz[105],pre[105],cnt = 0;
long long ret = 0;

void DFS(int u)
{
num[u] = low[u] = ++cnt;  sz[u] = 1;
for (int i = 0; i < adj[u].size(); i++)
{
if (pre[u] == v) continue;
if (!num[v])
{
pre[v] = u;  DFS(v);  sz[u] += sz[v];
if (low[v] > num[u]) ret += 1LL * sz[v] * (n - sz[v]);
low[u] = min(low[u],low[v]);
}
else if (pre[v] != u) low[u] = min(low[u],low[v]);
}
}

int main()
{
//    freopen("weather.in","r",stdin);
//    freopen("weather.ou","w",stdout);
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++)
{
int x,y;  scanf("%d %d", &x, &y);
if (x == y) continue;
}
memset(pre,-1,sizeof(pre));
DFS(1);
cout << ret << endl;
}


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

#include<cstdio>
#include<vector>
#define MAXV   111
#define MAXE   5050
using namespace std;
struct edge {
int u,v;
};
vector<int> g[MAXV];
bool a[MAXV][MAXV];
edge e[MAXE];
int m,n,c,r;
int num[MAXV];
int low[MAXV];
int up[MAXV];
int i,j;
scanf("%d",&n);
scanf("%d",&m);
for (i=1;i<=n;i=i+1)
for (j=1;j<=n;j=j+1)
a[i][j]=false;
for (i=1;i<=m;i=i+1) {
scanf("%d",&e[i].u);
scanf("%d",&e[i].v);
g[e[i].u].push_back(e[i].v);
g[e[i].v].push_back(e[i].u);
a[e[i].u][e[i].v]=true;
a[e[i].v][e[i].u]=true;
}
for (i=1;i<=n;i=i+1) num[i]=0;
c=0;
}
int find(int x) {
if (up[x]<0) return (x);
up[x]=find(up[x]);
return (up[x]);
}
void join(int a,int b) {
int x=find(a);
int y=find(b);
if (x==y) return;
up[x]=up[x]+up[y];
up[y]=x;
}
int bridge(int u,int v) {
int i;
for (i=1;i<=n;i=i+1) up[i]=-1;
for (i=1;i<=m;i=i+1) {
if ((e[i].u==u) && (e[i].v==v)) continue;
if ((e[i].u==v) && (e[i].v==u)) continue;
join(e[i].u,e[i].v);
}
for (i=1;i<=n;i=i+1)
if (up[i]<0) return ((-up[i])*(n+up[i]));
}
void visit(int u) {
int i,v;
c=c+1;
num[u]=c;
low[u]=n+1;
for (i=0;i<g[u].size();i=i+1) {
v=g[u][i];
if (!a[u][v]) continue;
a[v][u]=false;
if (num[v]==0) {
visit(v);
if (low[u]>low[v]) low[u]=low[v];
if (low[v]>num[u]) r=r+bridge(u,v);
}
else
if (low[u]>num[v]) low[u]=num[v];
}
}
void process(void) {
int i;
r=0;
for (i=1;i<=n;i=i+1)
if (num[i]==0) visit(i);
printf("%d",r);
}
int main(void) {