Submission #68572344

---

Source Code Expand

#include <bits/stdc++.h>
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x), end(x)
#define REP(i, n) for (int i = 0; i < int(n); i++)
#define REP1(i, a, b) for (int i = (a); i <= int(b); i++)

#if __has_include("shik/dump.h")
#include "shik/dump.h"  // IWYU pragma: keep
#else
#define dump(...) 0
#endif

using namespace std;

const int N = 2e5 + 10;

struct E {
  int to, w;
};

int n, m;
vector<int> es[N];
void input() {
  cin >> n >> m;
  REP(i, m) {
    int u, v;
    cin >> u >> v;
    es[u].push_back(v);
    es[v].push_back(u);
  }
}

int deg[N];

bool trimmed[N];
void trim() {
  queue<int> q;
  auto push = [&](int u) {
    if (!trimmed[u]) {
      trimmed[u] = true;
      q.push(u);
    }
  };
  REP1(i, 2, n - 1) if (deg[i] == 1) push(i);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    trimmed[u] = true;
    for (int v : es[u]) {
      if (v == 1 || v == n || trimmed[v]) continue;
      if (--deg[v] == 1) push(v);
    }
  }
  // REP1(i, 1, n) dump(i, trimmed[i]);
}

const int K = 45;

bool keep[N];
int kn, kid[N];
vector<E> ke[K];

void dfs(int r, int u, int f, int l) {
  for (int v : es[u]) {
    if (v == f) continue;
    if (keep[v]) {
      ke[kid[r]].push_back({kid[v], l + 1});
      continue;
    }
    dfs(r, v, u, l + 1);
  }
}

void shrink() {
  keep[1] = keep[n] = true;
  REP1(i, 2, n - 1) if (!trimmed[i] && deg[i] > 2) keep[i] = true;
  REP1(i, 1, n) if (keep[i]) kid[i] = ++kn;
  // REP1(i, 1, n) if (keep[i]) dump(i, kid[i]);

  REP1(i, 1, n) if (keep[i]) dfs(i, i, 0, 0);

  // REP1(i, 1, kn) {
  //   for (auto [to, w] : ke[i]) {
  //     dump(i, to, w);
  //   }
  // }
}

int sol[N];
bool vis[N];
void go(int u, int d) {
  if (u == kn) {
    sol[d]++;
    return;
  }
  vis[u] = true;
  for (auto [to, w] : ke[u]) {
    if (vis[to]) continue;
    if (d + w < n) go(to, d + w);
  }
  vis[u] = false;
}

void solve() {
  REP1(i, 1, n) deg[i] = SZ(es[i]);
  trim();
  shrink();
  go(1, 0);
  REP1(i, 1, n - 1) cout << sol[i] << (i == n - 1 ? '\n' : ' ');
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  input();
  solve();
  return 0;
}

Submission Info

Judge Result