#include <bits/stdc++.h>
// #include "communication.h"
#define rb(x) ((x)&(-(x)))
#define fi first
#define se second
#define sz(V) ((int)(V).size())
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 250055;
const int MAXM = 1000055;
int T[MAXN*4];
int Ts[MAXN*2], Tdeg[MAXN*2], _Ti[MAXN*2];
int GD[MAXM + MAXN*2];
int GDs[MAXN*2], GDdeg[MAXN*2], _GDi[MAXN*2];
int G[MAXM*2 + MAXN*2]; // save edges of graph in order of node
int Gs[MAXN*2]; // prefix sum of degree + i
int Gdeg[MAXN*2], _Gi[MAXN*2];
int RT[MAXN];
int cAlpha[MAXM];
int upperUp[MAXN*2], lowerUp[MAXN*2];
int upperAbove[MAXN*2], lowerAbove[MAXN*2];
int minOrderUp[MAXN*2], maxOrderUp[MAXN*2];
int minOrderAbove[MAXN*2], maxOrderAbove[MAXN*2];
int upCnt[MAXN*2], aboveCnt[MAXN*2];
int lcaUp[MAXN*2], lcaAbove[MAXN*2];
int dep[MAXN*2], prt[MAXN*2], prte[MAXN*2], dfo[MAXN*2], cnt[MAXN*2];
bitset<MAXM> treeEdge;
int A[MAXM], B[MAXM], C[MAXM];
bitset<MAXN*2> inV;
int Ans[MAXM];
int N, M, W, K, _N, _M;
int ud[MAXN*2];
int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
void uf(int a, int b) { ud[uf(b)] = uf(a); }
namespace TE3 {
void run() {
for(int i = ::N, r; i; i--) if(3 <= ::dep[i]) {
r = ::lowerUp[i];
if(1 == ::dep[r] && ::inV[r])
Ans[::C[::prte[i]]]++;
}
}
}
namespace TE2 {
int fenwick[MAXN*2];
pii IC[MAXN*2];
int ICT[MAXN*2], ICs[MAXN*2];
pii VIC[MAXN*4];
int VICs[MAXN*2], VICdeg[MAXN*2], _VICi[MAXN*2];
pii I[MAXN*6];
int Is[MAXN*2];
int dfoask[MAXN*4], dfoasks[MAXN*2], dfoaskdeg[MAXN*2], _dfoaski[MAXN*2];
int dfopush[MAXN*2];
int dfopop[MAXN*4], dfopops[MAXN*2], dfopopdeg[MAXN*2], _dfopopi[MAXN*2];
void upd(int i, int r) {
for(; i <= ::N; i += rb(i))
fenwick[i] += r;
}
int get(int i) {
int r = 0;
for(; i; i -= rb(i))
r += fenwick[i];
return r;
}
void run() {
// Sort IC + ICT by upperAbove dep
for(int i = ::N; i; i--)
if(4 <= ::dep[i] && ::inV[::prt[i]])
ICs[::dep[::upperAbove[i]]]++;
for(int i = 1; i < ::N; i++)
ICs[i+1] += ICs[i];
for(int i = ::N; i; i--) if(4 <= ::dep[i] && ::inV[::prt[i]]) {
int &idx = ICs[::dep[::upperAbove[i]]];
ICT[idx] = ::prt[i];
IC[idx] = { ::dep[::upperAbove[i]], ::dep[::lowerAbove[i]] };
idx--;
}
// Build VIC
for(int i = 1; ICT[i]; i++) VICdeg[ICT[i]]++;
for(int i = 1; i < ::N; i++) VICs[i+1] = VICs[i] + VICdeg[i] + 1;
memcpy(_VICi, VICs, ::N+1 << 2);
for(int i = 1; ICT[i]; i++) VIC[_VICi[ICT[i]]++] = IC[i];
// Make I
{
pii *it = I+1;
for(int i = 1, s, e; i <= ::N; i++) if(3 <= ::dep[i] && ::inV[i]) {
Is[i] = int(it - I);
s = 2; e = ::dep[i] - 1;
for(pii *cit = VIC + VICs[i];; cit++) {
if(!cit->fi || s > e) break;
if(cit->se <= cit->fi) continue;
if(s <= cit->fi) {
*it++ = { s, min(cit->fi, e) };
s = cit->se + 1;
} else {
if(s <= cit->se)
s = cit->se + 1;
}
}
if(s <= e) *it++ = {s, e};
it++;
}
}
// Sweeping
for(int i = ::N; i; i--) {
if(3 <= ::dep[i] && ::inV[i]) {
dfopush[::dfo[i]] = i;
dfopopdeg[::dfo[i] + ::cnt[i]]++;
}
if(2 <= ::dep[i])
dfoaskdeg[::dfo[::lcaUp[i]]]++;
}
for(int i = 1; i <= ::N+1; i++) {
dfoasks[i+1] = dfoasks[i] + dfoaskdeg[i] + 1;
dfopops[i+1] = dfopops[i] + dfopopdeg[i] + 1;
}
memcpy(_dfoaski, dfoasks, ::N+2 << 2);
memcpy(_dfopopi, dfopops, ::N+2 << 2);
for(int i = 1; i <= ::N; i++) {
if(3 <= ::dep[i] && ::inV[i]) dfopop[_dfopopi[::dfo[i] + ::cnt[i]]++] = i;
if(2 <= ::dep[i]) dfoask[_dfoaski[::dfo[::lcaUp[i]]]++] = i;
}
for(int dfotime = 1; dfotime <= ::N; dfotime++) {
if(dfopush[dfotime]) {
for(pii *it = I + Is[dfopush[dfotime]]; it->fi; it++) {
upd(it->fi, 1);
upd(it->se + 1, -1);
}
}
for(int *it = dfopop + dfopops[dfotime]; *it; it++) {
for(pii *iit = I + Is[*it]; iit->fi; iit++) {
upd(iit->fi, -1);
upd(iit->se + 1, 1);
}
}
for(int *askit = dfoask + dfoasks[dfotime]; *askit; askit++)
::Ans[::C[::prte[*askit]]] += get(::dep[*askit]);
}
}
}
namespace TE1C2 {
int fenwick[MAXN*2];
pii OC[MAXN*2]; // { dep, c }
int OCs[MAXN*2], OCn;
pii OV[MAXN*2]; // { dep, v }
int OVs[MAXN*2], OVn;
inline void upd(int i, int r) {
for(; i <= ::N; i += rb(i))
fenwick[i] += r;
}
inline int get(int i) {
int r = 0;
for(; i; i -= rb(i))
r += fenwick[i];
return r;
}
inline int get(int s, int e) { return get(e) - get(s-1); }
void run() {
// Sort OC & OV by dep
for(int i = ::N; i; i--) {
if(3 <= ::dep[i] && inV[::prt[i]]) {
OCs[::dep[i]]++;
OCn++;
}
if(4 <= ::dep[i]) {
OVs[::dep[::lowerUp[i]]]++;
OVn++;
}
}
for(int i = 1; i < ::N; i++) {
OCs[i+1] += OCs[i];
OVs[i+1] += OVs[i];
}
for(int i = ::N; i; i--) {
if(3 <= ::dep[i] && inV[::prt[i]])
OC[OCs[::dep[i]]--] = { ::dep[i], i };
if(4 <= ::dep[i])
OV[OVs[::dep[::lowerUp[i]]]--] = { ::dep[::lowerUp[i]], i };
}
for(pii *vit = OV+OVn, *cit = OC+OCn;; vit--) {
if(!vit->fi) break;
for(; vit->fi < cit->fi; cit--) {
upd(::dfo[::lcaAbove[cit->se]], 1);
upd(::dfo[cit->se], -1);
}
::Ans[::C[::prte[vit->se]]] += get(::dfo[vit->se], ::dfo[vit->se] + ::cnt[vit->se] - 1);
}
}
}
namespace TE1C1 {
void run() {
for(int v = ::N, u; v; v--) if(4 <= ::dep[v]) {
if(::upperUp[v] != ::lowerUp[v]) continue;
u = ::upperUp[v];
if(1 < ::dep[u] && inV[u]) ::Ans[::C[::prte[v]]]++;
}
}
}
namespace BE {
int AC[MAXN*2];
void dfs(int i, int d) {
for(int *eit = ::G + ::Gs[i];; eit++) {
if(!*eit) break;
::Ans[::C[*eit]] = W + (AC[d] - AC[::dep[::A[*eit]] + 1]);
}
for(int *eit = ::T + ::Ts[i];; eit++) {
if(!*eit) break;
AC[d+1] = AC[d] + (::inV[i] && 1 == ::aboveCnt[::B[*eit]] ? 1 : 0);
dfs(::B[*eit], d+1);
}
}
void run() {
for(int i = ::K; i; i--) dfs(::RT[i], 1);
}
}
namespace DFS2 {
int QU[MAXN*6], QUs[MAXN*2], QUdeg[MAXN*2], _QUi[MAXN*2];
int QA[MAXN*6], QAs[MAXN*2], QAdeg[MAXN*2], _QAi[MAXN*2];
bitset<MAXN*2> black;
void dfs(int i) {
for(int *eit = ::T + ::Ts[i], v;; eit++) {
if(!*eit) break;
v = ::B[*eit];
dfs(v);
::upCnt[i] += ::upCnt[v];
::aboveCnt[i] += ::aboveCnt[v];
::uf(i, v);
}
black[i] = true;
for(int *eit = QU + QUs[i], e, v;; eit++) {
e = *eit;
if(!e) break;
v = ::minOrderUp[e]^::maxOrderUp[e]^i;
if(black[v]) ::lcaUp[e] = ::uf(v);
}
for(int *eit = QA + QAs[i], e, v;; eit++) {
e = *eit;
if(!e) break;
v = ::minOrderAbove[e]^::maxOrderAbove[e]^i;
if(black[v]) ::lcaAbove[e] = ::uf(v);
}
}
void run() {
// Precompute for upCnt & aboveCnt
for(int i = ::M; i; i--) if(!::treeEdge[i]) {
::upCnt[::A[i]]--;
::upCnt[::B[i]]++;
::aboveCnt[::cAlpha[i]]--;
::aboveCnt[::B[i]]++;
}
// Build QU & QA
for(int i = ::N; i; i--) {
if(::minOrderUp[i]) {
QUdeg[::minOrderUp[i]]++;
QUdeg[::maxOrderUp[i]]++;
}
if(::minOrderAbove[i]) {
QAdeg[::minOrderAbove[i]]++;
QAdeg[::maxOrderAbove[i]]++;
}
}
for(int i = 1; i <= ::N; i++) {
QUs[i+1] = QUs[i] + QUdeg[i] + 1;
QAs[i+1] = QAs[i] + QAdeg[i] + 1;
}
memcpy(_QUi, QUs, ::N+1 << 2);
memcpy(_QAi, QAs, ::N+1 << 2);
for(int i = 1; i <= ::N; i++) {
if(::minOrderUp[i]) {
QU[_QUi[::minOrderUp[i]]++] = i;
QU[_QUi[::maxOrderUp[i]]++] = i;
}
if(::minOrderAbove[i]) {
QA[_QAi[::minOrderAbove[i]]++] = i;
QA[_QAi[::maxOrderAbove[i]]++] = i;
}
}
// Run DFS
iota(::ud, ::ud + ::N + 1, 0);
for(int i = ::K; i; i--) dfs(::RT[i]);
}
}
namespace MMO {
// sorted by dfo
int O[MAXN*2];
int pdep[MAXN*2];
inline void goup(int dp[], int i, int deplim) {
int v = i;
while(true) {
v = ::uf(v);
if(::dep[v] <= deplim) break;
dp[v] = i;
::uf(::prt[v], v);
}
}
void run() {
// Sort by dfo
for(int i = ::N; i; i--) O[::dfo[i]] = i;
// Precompute pdep
for(int i = ::N, t; i; i--) {
t = ::dep[i];
for(int *eit = ::G + ::Gs[i], pd;; eit++) {
if(!*eit) break;
pd = ::dep[::A[*eit]];
if(pd < t) t = pd;
}
pdep[i] = t;
}
// Compute minOrderUp
iota(::ud, ::ud + ::N + 1, 0);
for(int *it = O+1;; it++) {
if(!*it) break;
goup(::minOrderUp, *it, pdep[*it]);
}
// Compute maxOrderUp
iota(::ud, ::ud + ::N + 1, 0);
for(int *it = O+::N;; it--) {
if(!*it) break;
goup(::maxOrderUp, *it, pdep[*it]);
}
// Compute minOrderAbove
iota(::ud, ::ud + ::N + 1, 0);
for(int *it = O+1;; it++) {
if(!*it) break;
goup(::minOrderAbove, *it, pdep[*it] + 1);
}
// Compute maxOrderAbove
iota(::ud, ::ud + ::N + 1, 0);
for(int *it = O+::N;; it--) {
if(!*it) break;
goup(::maxOrderAbove, *it, pdep[*it] + 1);
}
}
}
namespace UL {
// sorted by dep
int O[MAXN*2], _I[MAXN*2];
inline void goup(int dp[], int i, int depi) {
for(int *eit = ::GD + ::GDs[i], v;; eit++) {
if(!*eit) break;
v = ::B[*eit];
while(true) {
v = ::uf(v);
if(::dep[v] <= depi) break;
dp[v] = i;
::uf(::prt[v], v);
}
}
}
void run() {
// Sort by dep
for(int i = ::N; i; i--) _I[::dep[i]]++;
for(int i = 2; i <= ::N; i++) _I[i] += _I[i-1];
for(int i = ::N; i; i--) O[_I[::dep[i]]--] = i;
// Compute upperUp
iota(::ud, ::ud + ::N + 1, 0);
for(int *it = O+1;; it++) {
if(!*it) break;
goup(::upperUp, *it, ::dep[*it]);
}
// Compute lowerUp
iota(::ud, ::ud + ::N + 1, 0);
for(int *it = O+::N;; it--) {
if(!*it) break;
goup(::lowerUp, *it, ::dep[*it]);
}
// Compute upperAbove
iota(::ud, ::ud + ::N + 1, 0);
for(int *it = O+1;; it++) {
if(!*it) break;
goup(::upperAbove, *it, ::dep[*it] + 1);
}
// Compute lowerAbove
iota(::ud, ::ud + ::N + 1, 0);
for(int *it = O+::N;; it--) {
if(!*it) break;
goup(::lowerAbove, *it, ::dep[*it] + 1);
}
}
}
namespace DFS1 {
int path[MAXN*2];
bitset<MAXN*2> chk;
int dfstime;
void dfs(int i, int pe) {
chk[i] = true;
path[::dep[i]] = i;
::cnt[i] = 1;
::dfo[i] = ++dfstime;
for(int *it = ::G + ::Gs[i], e, v;; it++) {
e = *it;
if(!e) break;
if(e == pe) continue;
v = ::A[e]^::B[e]^i;
if(chk[v]) {
if(::dep[v] < ::dep[i])
::cAlpha[e] = path[::dep[v]+1];
continue;
}
::treeEdge[e] = true;
::dep[v] = ::dep[i] + 1;
::prt[v] = i;
::prte[v] = e;
dfs(v, e);
::cnt[i] += ::cnt[v];
}
}
void run() {
for(int i = 1, rt; i <= ::K; i++) {
rt = ::RT[i];
dep[rt] = 1;
dfs(rt, 0);
}
}
}
namespace BCC {
int A[MAXM], B[MAXM], C[MAXM];
int RT[MAXN], _I[MAXN], _OI[MAXN*2];
int N, M, K;
int st[MAXM], stn;
int disc[MAXN], low[MAXN];
bitset<MAXM> cutedge;
bitset<MAXN> cutvertex;
int dfstime, cutcnt;
void dfs(int u, int pe) {
disc[u] = low[u] = ++dfstime;
int children = 0;
bool cut = false;
for(int *it = ::G + ::Gs[u], e, v;; it++) {
e = *it;
if(!e) break;
if(e == pe) continue;
v = ::A[e]^::B[e]^u;
if(disc[v]) {
if(disc[v] < low[u])
low[u] = disc[v];
if(disc[v] < disc[u])
st[++stn] = e;
} else {
children++;
st[++stn] = e;
dfs(v, e);
if(low[v] < low[u])
low[u] = low[v];
if(disc[u] < low[v])
cutedge[e] = true;
if((!pe && 1 < children)
|| (pe && disc[u] <= low[v])) {
cut = true;
if(st[stn] == e) stn--;
else {
K++;
const int startn = N;
while(true) {
int a = ::A[st[stn]];
int b = ::B[st[stn]];
if(_I[a] <= startn) {
N++;
_I[a] = N;
_OI[N] = a;
}
if(_I[b] <= startn) {
N++;
_I[b] = N;
_OI[N] = b;
}
M++;
A[M] = _I[a];
B[M] = _I[b];
C[M] = st[stn];
stn--;
if(!stn || st[stn+1] == e) break;
}
RT[K] = _I[u];
}
}
}
}
if(cut) {
cutvertex[u] = true;
cutcnt++;
}
}
void run(int rt) {
dfs(rt, 0);
if(stn) {
if(1 == stn) stn--;
else {
K++;
const int startn = N;
while(stn) {
int a = ::A[st[stn]];
int b = ::B[st[stn]];
if(_I[a] <= startn) {
N++;
_I[a] = N;
_OI[N] = a;
}
if(_I[b] <= startn) {
N++;
_I[b] = N;
_OI[N] = b;
}
M++;
A[M] = _I[a];
B[M] = _I[b];
C[M] = st[stn];
stn--;
}
RT[K] = _I[rt];
}
}
}
}
void solve() {
// Small case; Ans[*] = 0
if(2 == N) return;
// Build given graph
for(int i = M; i; i--) {
Gdeg[A[i]]++;
Gdeg[B[i]]++;
}
for(int i = 1; i <= N; i++)
Gs[i+1] = Gs[i] + Gdeg[i] + 1;
memcpy(_Gi, Gs, N+1 << 2);
for(int i = 1; i <= M; i++) {
G[_Gi[A[i]]++] = i;
G[_Gi[B[i]]++] = i;
}
// Find BCC from 1
BCC::run(1);
// Case; 1 + (N-1)
if(BCC::dfstime != N) {
assert(false);
if(1 == BCC::dfstime) {
BCC::run(2);
if(BCC::dfstime != N) {
fill(Ans+1, Ans+M+1, N);
return;
}
for(int i = M; i; i--)
Ans[i] = BCC::cutedge[i] ? N : N-1;
return;
}
if(N-1 != BCC::dfstime) {
fill(Ans+1, Ans+M+1, N);
return;
}
for(int i = M; i; i--)
Ans[i] = BCC::cutedge[i] ? N : N-1;;
return;
}
// Now, given graph is connected
// Case; cut edge
for(int i = 1; i <= M; i++) if(BCC::cutedge[i])
Ans[i] = (BCC::cutvertex[A[i]] && BCC::cutvertex[B[i]]) ? N : N-1;
// Rebuild graph
_N = N; _M = M;
N = BCC::N; M = BCC::M; K = BCC::K;
W = BCC::cutvertex.count();
for(int i = 1; i <= N; i++)
inV[i] = !BCC::cutvertex[BCC::_OI[i]];
memcpy(A, BCC::A, M+1 << 2);
memcpy(B, BCC::B, M+1 << 2);
memcpy(C, BCC::C, M+1 << 2);
memcpy(RT, BCC::RT, K+1 << 2);
memset(Gdeg, 0, N+1 << 2);
for(int i = M; i; i--) {
Gdeg[A[i]]++;
Gdeg[B[i]]++;
}
for(int i = 1; i <= N; i++)
Gs[i+1] = Gs[i] + Gdeg[i] + 1;
memcpy(_Gi, Gs, N+1 << 2);
memset(G, 0, M+M+N+1 << 2);
for(int i = 1; i <= M; i++) {
G[_Gi[A[i]]++] = i;
G[_Gi[B[i]]++] = i;
}
// 1st DFS
DFS1::run();
// Edge depth consistency
for(int i = M; i; i--)
if(dep[A[i]] > dep[B[i]])
swap(A[i], B[i]);
// Build tree (forest, only down) & Rebuild graph (only back edge) (up / down)
memset(Gdeg, 0, N+1 << 2);
for(int i = M; i; i--) {
if(treeEdge[i]) Tdeg[A[i]]++;
else { Gdeg[B[i]]++; GDdeg[A[i]]++; }
}
for(int i = 1; i <= N; i++) {
Ts[i+1] = Ts[i] + Tdeg[i] + 1;
Gs[i+1] = Gs[i] + Gdeg[i] + 1;
GDs[i+1] = GDs[i] + GDdeg[i] + 1;
}
memcpy(_Ti, Ts, N+1 << 2);
memcpy(_Gi, Gs, N+1 << 2);
memcpy(_GDi, GDs, N+1 << 2);
memset(G, 0, M+N+1 << 2);
for(int i = 1; i <= M; i++) {
if(treeEdge[i]) T[_Ti[A[i]]++] = i;
else {
G[_Gi[B[i]]++] = i;
GD[_GDi[A[i]]++] = i;
}
}
// Compute upper/lower Up/Above
UL::run();
// Compute min/max Order Up/Above
MMO::run();
// 2nd DFS
DFS2::run();
// Answer; Back edge
BE::run();
// Answer; Tree edge 1 - Case 1
TE1C1::run();
// Answer; Tree edge 1 - Case 2
TE1C2::run();
// Answer; Tree edge 2
TE2::run();
// Answer; Tree edge 3
TE3::run();
// Answer; Tree edge - Base W
for(int i = ::M; i; i--) if(treeEdge[i])
Ans[C[i]] += W;
M = _M;
}
vector<int> find_num_critical(int N, vector<pii> E) {
::N = N;
::M = sz(E);
for(int i = 1; i <= ::M; i++)
tie(::A[i], ::B[i]) = E[i-1];
solve();
return vector<int>(::Ans+1, ::Ans+::M+1);
}
int32_t main() {
int N, M;
vector<pii> E;
cin >> N >> M;
for (int i = 1; i <= M; ++i) {
int u, v;
cin >> u >> v;
E.emplace_back(u, v);
}
auto ans = find_num_critical(N, E);
for (auto val : ans) cout << val << "\n";
}