代码

// References:
// [1] duck.ac user saffah_cc_v41_agg1, submission #106832, https://duck.ac/submission/106832 . Directly reuse its accepted grouped CSR, five-byte adjacency metadata and DFS. Its header also identified fusing the metadata's last-entry flag pass as future work; this submission implements that idea afresh. The inherited citations remain below. No additional license terms displayed on the public source.
// [2] duck.ac user saffah_codex_6s_agg2, submission #105007, https://duck.ac/submission/105007 . Earlier grouped CSR and output ideas retained in [1] originate with our account. No license terms displayed.
// Approach:
// While packing adjacency records, advance a cursor over the monotonically ordered CSR row ends. Mark each row's final record in the same write that stores its five-byte metadata. This removes the later full pass over every vertex and its scattered writes into metadata. Empty CSR rows are skipped by advancing the cursor until it covers the current edge.
// Purpose:
// Check exact traversal output and measure whether a single metadata construction pass beats #106832 on the official unicyclic cases.
// ===== REFERENCES =====
// [1] 本账号 **saffah_cc_v41_agg1** 提交 **#106799** <https://duck.ac/submission/106799>
//     （**32.695431 ms** = 本题现役最好件，`work/p2z_g2048_sub.cpp`，GSIZE 2048）——
//     本文件正文 = **该提交正文的逐字节副本 + 一个 token**（peel 内层补 `break;`，见"思路"）。
//     其父本链：#106723 <https://duck.ac/submission/106723>（32.885413，`work/p2w_best.cpp`）
//     ⇒ 最新一发 #106805（GSIZE 1024，32.983 ≠ 未胜）。
// [2] duck.ac 用户 **saffah_codex_6s_agg2** 提交 **#105007** <https://duck.ac/submission/105007>
//     （33.009577 ms = 本题实时 T）。
// [3] `BRIEF.md §2.19.350`（先问一个区被什么限住再选代理：LFB ⇒ 数在飞访存）、
//     `§2.19.351`（剂量臂定量版）、`§2.19.365`（"补成员"第四条前提：该行冷不冷）、
//     `§2.19.366`（漏成员刀型的干涸判据）。
// [4] 本工作区 `problems/2002/notes.md §16.8`（peel = 7.0%，唯二对标签局部性敏感的相位）、
//     `§17.12`（peel 环逐站点枚举）；本席上一轮 `1001c` 的忠实复刻台方法（`§2.19.373`）。
// ======================
// ===== 思路 =====
// 【本发 = #106799 正文逐字节 + **一个 token**：peel 最内层补一条 `break;`（语义恒等，见下）】
// 目的：**把 peel 内层里"注定什么都不做"的迭代删掉** —— 按 `§2.19.350` 先问该环被什么限住：
//   该环 = 随机 RMW `deg[adj[c]]`（2 MB `deg[]`、Σdeg ≈ 2m 次迭代、实测 ≈8.3 拍/迭代），
//   它的**主项是每次迭代那一次随机 `deg[v]` 取数的延迟**（L2/L3 档，MLP 受 LFB 条数封顶）——
//   即"受限面 = 在飞访存条数"，所以代理变量是**迭代次数**（不是 uop 数、不是字节数）。
// 恒等性（本文件的前提，逐条可查）：
//   ① 初始队列只收 `d == 1` 的顶点（正文 `if (d == 1) qq[qt++] = u;`）；
//   ② 之后只在该顶点度数**刚降到 1** 时入队（正文 `qt += (u32)(dv == 1);`）；
//   ③ `deg[]` 在 peel 全程**只减不增** ⇒ **弹出一个顶点 u 时 `deg[u] ∈ {0,1}`**
//      ⇒ u 的**活邻居至多 1 个** ⇒ 扫到它之后，**其余邻居必然 `deg[v] == 0`**，
//      而 `if (dv)` 守卫体对它们是**空操作**（不改 deg、不入队）⇒ 后续迭代**全部是空转**。
//   ⇒ 扫到唯一活邻居后 `break` **不改变 `qq[]` 的内容与顺序、不改变 peel 终态 `deg[]`**
//      ⇒ 输出逐位不变（已过生产输入逐字节闸门，见 FINDINGS）。
// 定价预期：省掉的是**已剥邻居的那些随机 `deg[v]` 取数**（占内层迭代的约一半，取决于活邻居在
//   排序后邻接表里的位置）；若 peel ≈ 7.0%（2.3 ms），省掉其中 X% 即 ≈ 0.07·X ms。
// 【重叠自检】相对 #106799 只多一个 `break;`（不动预取站、不动布局、不动任何常数）✓
// ================
#include <emmintrin.h>
#ifdef LOCAL_TEST
#include <cstdio>
#include <cstdlib>
#include <cstring>
typedef unsigned long u64;
static char g_in[48 << 20];
static char g_out[48 << 20];
#else
typedef unsigned long u64;
#endif

typedef unsigned int u32;
static int g_nosort = 1;   // ABLATION probe: 1 = skip the per-list sort (WA)

#define MAXN 500005
#define MAXE 1000005
/* [GSIZE] 12 -> 11: the group partition is the only knob the lane notes flag as never
   investigated (16.8).  It trades two things at once -- (a) the number of concurrent
   written streams in the T[] scatter (G = n/GSIZE groups: 245 instead of 123) and
   (b) the L1 residency of the per-group deg[]/SC[] window (2 x 8 KB instead of 2 x 16 KB).
   LOG2G >= 13 is structurally impossible: the packing puts the in-group label at bits
   20..31, i.e. exactly 12 bits, so GMASK must stay <= 4095. */
#define LOG2G 11
#define GSIZE (1 << LOG2G)
#define GMASK (GSIZE - 1)
#define MAXG ((MAXN / GSIZE) + 2)


static u32 deg[MAXN] __attribute__((aligned(64)));
static u32 start[MAXN + 2] __attribute__((aligned(64)));
static u32 adj[MAXE] __attribute__((aligned(64)));


union Y2BU {
  struct { u32 TT[MAXE]; u32 EEu[MAXE]; u32 EEv[MAXE]; } s;
  unsigned char A5B_[5 * MAXE + 64];
};
static union Y2BU YU;
#define T   YU.s.TT
#define Eu  YU.s.EEu
#define Ev  YU.s.EEv
#define A5B YU.A5B_
static u32 SC[MAXN + 2];
static u32 gpos[MAXG];
static u32 gcnt[MAXG], gcur[MAXG];
static u32 DV[MAXN];
static u32 par[MAXN];
static u32 STK[3 * MAXN] __attribute__((aligned(64)));
#define stk (STK)
#define stkc (STK + MAXN)
#define stke (STK + 2 * MAXN)
static u32 qq[MAXN + 32] __attribute__((aligned(64)));   // +16 so the peel's lookahead read stays in bounds
static u32 vs[MAXN];
static unsigned char vis[MAXN];

static const char D2[] =
  "00010203040506070809"
  "10111213141516171819"
  "20212223242526272829"
  "30313233343536373839"
  "40414243444546474849"
  "50515253545556575859"
  "60616263646566676869"
  "70717273747576777879"
  "80818283848586878889"
  "90919293949596979899";

#ifdef LOCAL_TEST
static const unsigned char *ip_, *ie_;
static char *op_;
#else
struct DI {
  u64 abi;
  const char *s; u64 sn;
  char *o; u64 ol; u64 os;
  char *e; u64 el; u64 es;
  const char *IB; u64 IBl;
  char *OB; u64 OBl;
  u64 tsc;
} __attribute__((packed));
static DI *D;
static const unsigned char *ip_, *ie_;
static char *op_;
#endif

static inline u32 ni() {
  const unsigned char *p = ip_;
  while (*p <= ' ') p++;
  u32 v = (u32)(*p++ - '0');
  while (*p > ' ') v = v * 10 + (u32)(*p++ - '0');
  ip_ = p;
  return v;
}
static unsigned short D2W[100];
static u32 D3W[1000];
static inline void initD2W(void) {
  for (int i = 0; i < 100; i++) D2W[i] = (unsigned short)((unsigned char)D2[i*2] | ((unsigned char)D2[i*2+1] << 8));
  for (int i = 0; i < 1000; i++) D3W[i] = (u32)('0' + i / 100) | ((u32)D2W[i % 100] << 8);
}
// v <= 999999 (bounded by n <= 500000).  Builds the 6 digit bytes + a trailing space
// entirely in a register and emits them with ONE unaligned 8-byte store, instead of the
// shipped reverse-into-then-copy-byte-by-byte form.  Verified byte-identical to the
// shipped formatter for every v in 1..600000; measured 3.03x faster (20.68 -> 6.83 ns/num).
// ---- non-temporal staged output -------------------------------------------
// The 3.4 MB output used to stream through L3 with an RFO read per line, and L3 is
// exactly the size of the DFS's working set (adj 4 MB + start 2 MB).  Staging the emit
// in an L1-resident buffer and flushing it with movntdq drops both the RFO traffic and
// the eviction.  A measured probe that only removed the streaming (keeping the whole
// formatter) was worth -0.85 ms on the k=250k shape, -0.70 pure cycle, -0.17 tree.
static char sbuf[8192 + 128];
static char *ofp;
static u32 soff = 0;
static void oflush(void) {
  if (soff < 32u) return;
  if ((size_t)ofp & 31u) {                 // one-off 32-byte alignment prologue
    u32 pad = 32u - (u32)((size_t)ofp & 31u);
    if (pad > soff) return;
    __builtin_memcpy(ofp, sbuf, pad);
    ofp += pad; soff -= pad;
    __builtin_memmove(sbuf, sbuf + pad, soff);
  }
  u32 n = soff & ~31u;
  for (u32 i = 0; i < n; i += 32) {
    __m128i x = _mm_loadu_si128((const __m128i *)(sbuf + i));
    __m128i y = _mm_loadu_si128((const __m128i *)(sbuf + i + 16));
    _mm_stream_si128((__m128i *)(ofp + i), x);
    _mm_stream_si128((__m128i *)(ofp + i + 16), y);
  }
  ofp += n; soff -= n;
  if (soff) __builtin_memmove(sbuf, sbuf + n, soff);
}
static void oflushall(void) {
  oflush();
  if (soff) { __builtin_memcpy(ofp, sbuf, soff); ofp += soff; soff = 0; }
  _mm_sfence();
  op_ = ofp;
}
static __attribute__((always_inline)) inline void emit(u32 v) {
  u32 hi3 = v / 1000u, lo3 = v - hi3 * 1000u;
  u64 w = (u64)D3W[hi3] | ((u64)D3W[lo3] << 24) | ((u64)0x20u << 48);
  u32 kk = (u32)(v < 100000u) + (u32)(v < 10000u) + (u32)(v < 1000u)
         + (u32)(v < 100u) + (u32)(v < 10u);
  if (__builtin_expect(v >= 100000u, 1)) {   // 6 digits: kk == 0 -> z == w, advance is exactly 7
    __builtin_memcpy(sbuf + soff, &w, 8);
    soff += 7u;
    if (__builtin_expect(soff >= 8192u, 0)) oflush();
    return;
  }
  u64 z = w >> (8u * kk);
  __builtin_memcpy(sbuf + soff, &z, 8);
  soff += 7u - kk;
  if (__builtin_expect(soff >= 8192u, 0)) oflush();
}
// The radix path is what stopped gcc inlining bsort, so EVERY one of the n call sites
// paid a real call+return -- and half of them (deg==1) return immediately.  Split it:
// the small path is force-inlined (it is ~20 instructions) and only the rare long-list
// case goes through a call.
static __attribute__((noinline)) void bsort_big(u32 *a, u32 len) {
  // LSD radix, 3 passes of 8 bits (values < 2^20)
  static u32 scr[MAXE];
  u32 *src = a, *dst = scr;
  for (u32 sh = 0; sh < 24; sh += 8) {
    u32 cnt[256];
    for (u32 i = 0; i < 256; i++) cnt[i] = 0;
    for (u32 i = 0; i < len; i++) cnt[(src[i] >> sh) & 255]++;
    u32 s = 0;
    for (u32 i = 0; i < 256; i++) { u32 c = cnt[i]; cnt[i] = s; s += c; }
    for (u32 i = 0; i < len; i++) { u32 b = (src[i] >> sh) & 255; dst[cnt[b]++] = src[i]; }
    u32 *t = src; src = dst; dst = t;
  }
  if (src != a) for (u32 i = 0; i < len; i++) a[i] = src[i];
}
/* ARM c5 (lane l2002_lane_b2): BRANCHLESS SMALL-LIST NETWORK.
   The corrected ladder prices `bsort + DV + qq seed` at 5 873 us (harness, k=250000) and a
   BOARD ablation of the sort alone at 1.822 ms (sid 102290, WA, 39.425 -> 37.603 ms) -- 4x the
   gap.  The work is NOT the comparisons (a random recursive tree is ~50 % deg-1 and ~25 %
   deg-2, so the genuine sort work is ~1 op per list): it is the insertion sort's
   `for (i = 1; i < len; i++)` exit branch, whose trip count is a random 1..6 and therefore
   mispredicts on the hot per-vertex path.  For 2 <= len <= 4 this replaces the loop with a
   FIXED 5-compare-exchange network on register-resident values, padded with a 0xFFFFFFFF
   sentinel and written back with masked (cmov) stores, so nothing outside [a, a+len) is
   touched.  Branch-free, no loop, fixed cost. */
#define NRM_CE(X, Y) do { u32 _x = (X), _y = (Y); u32 _l = _x < _y ? _x : _y; u32 _h = _x < _y ? _y : _x; (X) = _l; (Y) = _h; } while (0)
static __attribute__((always_inline)) inline void bsort4(u32 *a, u32 len) {
  u32 x0 = a[0];
  u32 x1 = len > 1 ? a[1] : 0xFFFFFFFFu;
  u32 x2 = len > 2 ? a[2] : 0xFFFFFFFFu;
  u32 x3 = len > 3 ? a[3] : 0xFFFFFFFFu;
  NRM_CE(x0, x1); NRM_CE(x2, x3); NRM_CE(x0, x2); NRM_CE(x1, x3); NRM_CE(x1, x2);
  a[0] = x0;
  if (len > 1) a[1] = x1;
  if (len > 2) a[2] = x2;
  if (len > 3) a[3] = x3;
}
static __attribute__((always_inline)) inline void bsort(u32 *a, u32 len) {
  if (len < 2) return;
  if (len == 2) {
    u32 x = a[0], y = a[1];
    a[0] = x < y ? x : y;
    a[1] = x < y ? y : x;
    return;
  }
  if (len <= 4) { bsort4(a, len); return; }
  if (len <= 24) {
    for (u32 i = 1; i < len; i++) {
      u32 x = a[i], j = i;
      while (j && a[j - 1] > x) { a[j] = a[j - 1]; j--; }
      a[j] = x;
    }
    return;
  }
  bsort_big(a, len);
}

static __attribute__((noinline)) void y2b_a5_dfs(u32 n, u32 m, u32 cu, u32 cv) {
  u32 owner = 1;
  u32 last = start[2] - 1;
  for (u32 cc = 0; cc < (m << 1); cc++) {
    while (cc > last) { ++owner; last = start[owner + 1] - 1; }
    u32 w = adj[cc];
    u32 st = start[w];
    unsigned char *pp = A5B + (size_t)cc * 5;
    u32 stx = (start[w + 1] == st + 1) ? 0xFFFFFu : st;
    *(u32 *)pp = w | (stx << 19);
    pp[4] = (unsigned char)((stx >> 13) | (cc == last ? 0x80u : 0u));
  }
  u32 sp = 0;
  ofp = op_;
  stk[sp] = 1; stkc[sp] = start[1]; stke[sp] = start[2]; sp++;
  emit(1);
  while (sp) {
    u32 u = stk[sp - 1];
    u32 c = stkc[sp - 1];
    u32 pu = sp >= 2 ? stk[sp - 2] : 0;
    // A5: 每顶点一次依赖随机读。孩子自己的 start 随父表条目一起到达（扫描是顺序的），
    // 且它的地址在本轮确定 => 可以提前一整个迭代预取。stke[]（end 上界）由 last 位取代。
    u32 v = 0, sv = 0, last = 0;
    for (;;) {
      if (c == 0xFFFFFFFFu) break;                 // 该表已走完（与旧的 c >= e 同义）
      unsigned long long yx = *(const unsigned long long *)(A5B + (size_t)c * 5);
      u32 x = (u32)(yx & 524287u);
      last = (u32)((yx >> 39) & 1u);
      if (!(x == pu || (u == cu && x == cv) || (u == cv && x == cu))) {
        v = x; sv = (u32)((yx >> 19) & 1048575u); break;
      }
      if (last) { c = 0xFFFFFFFFu; break; }        // 跳过的那条正是本表最后一条
      c++;
    }
    if (v) {
      stkc[sp - 1] = last ? 0xFFFFFFFFu : c + 1;   // 父帧游标；哨兵 = 该表已空
      emit(v);
      // V2: deg[v]==1 <=> v 自己表的首条目就是最后一条（同线一次读，取代 sv1-sv==1）
      if (sv == 0xFFFFFu) continue;   // [y3] deg-1 child: no 2nd load
      __builtin_prefetch(A5B + (size_t)sv * 5);
      stk[sp] = v; stkc[sp] = sv; sp++;
    } else sp--;
  }
  oflushall();
}

static void main_solve() {
  static int _d2w = 0; if (!_d2w) { _d2w = 1; initD2W(); }
  u32 n = ni(), m = ni();
  if (n == 0) n = 1;
  const unsigned char *hdr = ip_;
  // ---- grouped degree count: the RMW lands on 123 L1-resident counters, not on the 2 MB deg[] ----
  for (u32 i = 0; i < m; i++) {
    u32 u = ni(), v = ni();
    // NOTE: the group index is taken from the 0-BASED label, exactly as the shipped
    // T[] scatter does (u = Eu[i] = label-1, then gpos[u >> LOG2G]++).  Using the raw
    // 1-based label here shifts every vertex whose label is 1 (mod 4096) into the next
    // group -- the 54-shape gate caught it as 9/54 fail.
    gcnt[(u - 1) >> LOG2G]++; gcnt[(v - 1) >> LOG2G]++;
    Eu[i] = u - 1; Ev[i] = v - 1;
  }
  // group buckets: group g covers vertices [g*GSIZE+1, min(n, (g+1)*GSIZE)]
  u32 G = ((n - 1) >> LOG2G) + 1;
  {
    u32 s = 0;
    for (u32 g = 0; g < G; g++) { gpos[g] = s; gcur[g] = s; s += gcnt[g]; }
    gpos[G] = s;                                 // == 2m == old start[n+1]
  }
  // parse again, scatter directed edges into group buckets  (same buckets, same order)
  for (u32 i = 0; i < m; i++) {
    u32 u = Eu[i], v = Ev[i];
    T[gcur[u >> LOG2G]++] = (u32)((u & GMASK) << 20) | (v + 1);
    T[gcur[v >> LOG2G]++] = (u32)((v & GMASK) << 20) | (u + 1);
  }
  // per-group: rebuild deg[] inside the 16 KB window, prefix-sum it, scatter.  deg[] ends
  // bit-identical to what the old pass-1 RMW produced (the sort loop and the peel read it).
  u32 carry = 0;
  for (u32 g = 0; g < G; g++) {
    u32 base = (g << LOG2G) + 1;
    u32 hi = base + GSIZE;
    if (hi > n + 1) hi = n + 1;
    u32 lo = gpos[g], e = gpos[g + 1];
    for (u32 t = lo; t < e; t++) {
      u32 x = T[t];
      deg[base + (x >> 20)]++;
    }
    u32 s = carry;
    for (u32 u = base; u < hi; u++) { u32 d = deg[u]; start[u] = s; SC[u] = s; s += d; }
    carry = s;
    for (u32 t = lo; t < e; t++) {
      u32 x = T[t];
      u32 u = base + (x >> 20);
      adj[SC[u]++] = x & 0xFFFFF;
    }
  }
  start[n + 1] = carry;
  // sort each adjacency list  (fused: the ring case also seeds DV[] and the leaf queue here,
  // so deg[] is read once instead of twice and the separate init pass disappears)
  u32 qh = 0, qt = 0;
  if (m == n - 1) {
    if (g_nosort) {
      u32 b = 0;                       // start[1]=0 and start[u+1]=start[u]+deg[u]
      for (u32 u = 1; u <= n; u++) { u32 d = deg[u]; bsort(adj + b, d); b += d; }
    }
  } else {
    // deg[] is ALSO the peel's DV[] (see below).  The list base is a RUNNING SUM of deg[]
    // (start[1]=0, start[u+1]=start[u]+deg[u]), so start[] is never re-read here: the shipped
    // loop streamed a full extra 2 MB of start[] to obtain a value it was already holding.
    // deg[] is DEAD from the moment this loop ends (the only later readers of a degree
    // are the peel, and the peel destroys it) -- so DV[] is not a second array at all.
    // The shipped code copied deg[] into DV[] : a full n-vertex 2 MB write for nothing.
    if (g_nosort) {
      u32 b = 0;
      for (u32 u = 1; u <= n; u++) {
        u32 d = deg[u];
        bsort(adj + b, d);
        b += d;
        if (d == 1) qq[qt++] = u;
      }
    }
  }

  if (m == n - 1) {
    // A5 for the TREE branch, INLINED (not called): keeping the block in place keeps
    // main_solve's code shape close to the version without it, so the m==n path's layout
    // (and therefore tc19) is disturbed much less.  cu = cv = 0 makes the cut test
    // identically false for every u >= 1, so this IS the tree DFS.
    u32 cu = 0, cv = 0;
      for (u32 cc = 0; cc < (m << 1); cc++) {
        u32 w = adj[cc];
        u32 st = start[w];
        unsigned char *pp = A5B + (size_t)cc * 5;
        u32 stx = (start[w + 1] == st + 1) ? 0xFFFFFu : st;  // [y3] dead st for a deg-1 child
        *(u32 *)pp = w | (stx << 19);
        pp[4] = (unsigned char)(stx >> 13);
      }
      for (u32 uu = 1; uu <= n; uu++) if (start[uu + 1] > start[uu]) A5B[((size_t)(start[uu + 1] - 1)) * 5 + 4] |= 0x80;
      u32 sp = 0;
      ofp = op_;
      stk[sp] = 1; stkc[sp] = start[1]; stke[sp] = start[2]; sp++;
      emit(1);
      while (sp) {
        u32 u = stk[sp - 1];
        u32 c = stkc[sp - 1];
        u32 pu = sp >= 2 ? stk[sp - 2] : 0;
        // A5: 每顶点一次依赖随机读。孩子自己的 start 随父表条目一起到达（扫描是顺序的），
        // 且它的地址在本轮确定 => 可以提前一整个迭代预取。stke[]（end 上界）由 last 位取代。
        u32 v = 0, sv = 0, last = 0;
        for (;;) {
          if (c == 0xFFFFFFFFu) break;                 // 该表已走完（与旧的 c >= e 同义）
          unsigned long long yx = *(const unsigned long long *)(A5B + (size_t)c * 5);
          u32 x = (u32)(yx & 524287u);
          last = (u32)((yx >> 39) & 1u);
          if (!(x == pu || (u == cu && x == cv) || (u == cv && x == cu))) {
            v = x; sv = (u32)((yx >> 19) & 1048575u); break;
          }
          if (last) { c = 0xFFFFFFFFu; break; }        // 跳过的那条正是本表最后一条
          c++;
        }
        if (v) {
          stkc[sp - 1] = last ? 0xFFFFFFFFu : c + 1;   // 父帧游标；哨兵 = 该表已空
          emit(v);
          // V2: deg[v]==1 <=> v 自己表的首条目就是最后一条（同线一次读，取代 sv1-sv==1）
          if (sv == 0xFFFFFu) continue;   // [y3] deg-1 child: no 2nd load
          __builtin_prefetch(A5B + (size_t)sv * 5);
          stk[sp] = v; stkc[sp] = sv; sp++;
        } else sp--;
      }
      oflushall();
    return;
  }

  // ---- m == n : base ring tree ----
  while (qh < qt) {
    u32 u = qq[qh++];
    // Hide the random start[u] miss: issue it 16 pops early.  qq[] is sequential, so this
    // read is nearly free, and qq[] is zero-filled BSS past qt so the prefetch address is
    // always a valid index into start[].
    // two-stage lookahead: the pop is a chain  qq -> start[u] -> adj[start[u]] -> deg[v].
    // Stage 1 (h2) prefetched start[]; stage 2 loads that start 16 pops early (a real load,
    // so its value is available to form the adj[] address) and prefetches adj[] from it.
    u32 la24 = qq[qh + 24];
    __builtin_prefetch(&start[la24]);
    u32 la = qq[qh + 16];
    if (la <= n) __builtin_prefetch(&adj[start[la]]);
    u32 la8 = qq[qh + 8];
    if (la8 <= n) __builtin_prefetch(&deg[adj[start[la8]]]);
    // stage 4: the pipeline above covers start[u] / adj[start[u]] / deg[neighbour], but NOT
    // the popped vertex's OWN deg[u] -- which is read-modify-written right here and whose
    // line was last touched when u was pushed (up to n pops ago, so a likely miss).
    u32 laD = qq[qh + 12];
    if (laD <= n) __builtin_prefetch(&deg[laD]);
    deg[u] = 0;
    /* p2w: start[u] and start[u+1] are adjacent u32s -- two separate 4-byte loads in the
       shipped code.  One unaligned 8-byte load delivers both (the same shape as #106621,
       which REGRESSED +1.3% in the DFS descend block; this is the peel loop instead, which
       is a different loop, and it is the one axis the fleet notes list as still open). */
    u64 s8p = *(const u64 *)(const void *)(start + u);
    u32 e2 = (u32)(s8p >> 32);
    for (u32 c = (u32)s8p; c < e2; c++) {
      u32 v = adj[c];
      { u32 dv = deg[v]; if (dv) { dv--; deg[v] = dv; qq[qt] = v; qt += (u32)(dv == 1); break; } }
    }
  }
  u32 c0, br = 0;
  if (deg[1]) { c0 = 1; br = 0; }
  else {
    u32 sp = 0;
    par[1] = 0; stk[sp++] = 1;
    c0 = 0;
    while (sp && !c0) {
      u32 u = stk[--sp];
      for (u32 c = start[u]; c < start[u + 1]; c++) {
        u32 v = adj[c];
        if (v == par[u]) continue;
        if (deg[v]) { c0 = v; br = u; break; }
        par[v] = u; stk[sp++] = v;
      }
    }
  }
  u32 a = 0, bb2 = 0;
  for (u32 c = start[c0]; c < start[c0 + 1]; c++) {
    u32 v = adj[c];
    if (deg[v]) { if (!a) a = v; else bb2 = v; }
  }
  u32 first = a < bb2 ? a : bb2;
  u32 lastv = (a == first) ? bb2 : a;          // == vs[k-1], known without walking
  u32 v1 = first, vk1 = lastv;
  u32 backA0 = vk1;
  {
    // adjacency is sorted ascending => the first non-cycle x in (v1, vk1) IS the minimum.
    u32 best = 0;
    u32 lo = start[c0], hi = start[c0 + 1];
    while (lo < hi) { u32 mid = (lo + hi) >> 1; if (adj[mid] <= v1) lo = mid + 1; else hi = mid; }
    for (u32 c = lo; c < start[c0 + 1]; c++) {
      u32 x = adj[c];
      if (x >= vk1) break;
      if (deg[x] || x == br) continue;
      best = x; break;
    }
    if (best) backA0 = best;
  }
  // ---- LAZY FUSED cycle enumeration + `chosen` analysis --------------------
  // The shipped code materialised the WHOLE cycle (vs[0..k-1]) and only THEN ran
  // the `chosen` loop, which breaks at the first qualifying b.  The loop's two
  // tests depend only on the pair (vs[b], vs[b+1]), so enumerate one step at a
  // time and stop exactly where the loop stops.  vs[] is needed for nothing
  // else: vs[0]=c0, vs[1]=first, vs[k-1]=lastv are all known up front.
  // EQUIVALENCE IS A PROOF, NOT A MEASUREMENT: identical b's in identical order
  // with identical conditions, and the cut edge is the same pair in both cases.
  u32 cu, cv;
  {
    u32 glast = 0, lastb = 0, chosen = 0;
    u32 prev = c0, cur = first, bcnt = 1;
    u32 oa = lastv, ob = c0;                   // the no-break cut: (vs[k-1], vs[0])
    while (1) {
      u32 nxt = 0;
      for (u32 c = start[cur]; c < start[cur + 1]; c++) {
        u32 v = adj[c];
        if (deg[v] && v != prev) { nxt = v; break; }
      }
      if (nxt == c0) break;                    // cur == vs[k-1] => b would be k-1, out of range
      u32 gb = 0;
      u32 lo = start[cur], hi = start[cur + 1];
      while (lo < hi) { u32 mid = (lo + hi) >> 1; if (adj[mid] <= nxt) lo = mid + 1; else hi = mid; }
      for (u32 c = lo; c < start[cur + 1]; c++) { u32 x = adj[c]; if (deg[x]) continue; gb = x; break; }
      if (!gb) {
        u32 bbx = lastb ? glast : backA0;
        if (bbx < nxt) { oa = cur; ob = nxt; chosen = 1; break; }
      } else { glast = gb; lastb = 1; }
      prev = cur; cur = nxt; bcnt++;
    }
    (void)bcnt; (void)chosen;
    cu = oa; cv = ob;
  }
  // ---- A5: 5 字节打包邻接条目 = label(19) | start(label)(20) | last(1) ----
  // 2m = 1e6 条 × 5 B = 5 MB < judge L3 6 MB（u64 版 8 MB 已实测 +18.6%，越临界线）。
  // last = 该条目是其属主邻接表的最后一条；它就是帧的 end 上界（stke[] 由此取消）。
  // ---- ring length k: decides A5.  k = n - qt for FREE: the peel pushes exactly the
  // n-k non-cycle vertices (each once, when its degree falls to 1, or as a deg==1 seed)
  // and never a cycle vertex.  (An earlier version counted `deg[v] != 0` with an O(n)
  // pass; that scan alone was ~0.3% of the m=n points, ~2 MB of extra reads.)
  // A5's win is monotone in the ring fraction (measured per point: tc17/18 k=n -> -9.3,
  // tc20 k=0.79n -> -3.7, tc19 k=0.52n -> +3.8), so gate it at k >= 3n/4  <=>  qt <= n/4.
  if (qt <= (n >> 2)) {
    y2b_a5_dfs(n, m, cu, cv);
  } else {
      u32 sp = 0;
      ofp = op_;
      stk[sp] = 1; stkc[sp] = start[1]; stke[sp] = start[2]; sp++;
      emit(1);
      while (sp) {
        u32 u = stk[sp - 1];
        u32 c = stkc[sp - 1];
        u32 e = stke[sp - 1];
        u32 pu = sp >= 2 ? stk[sp - 2] : 0;
        while (c < e) {
          u32 v = adj[c];
          __builtin_prefetch(&start[adj[c + 1]]);
          /* second start[] hint omitted; next-neighbour hint remains */
          if (v == pu || (u == cu && v == cv) || (u == cv && v == cu)) c++;
          else break;
        }
        if (c < e) {
                u32 v = adj[c];
          u32 sv = start[v], sv1 = start[v + 1];
          // l2002_c: hoist the child's first neighbour into a LOAD and use it to
          // prefetch start[] for the vertex the child will descend into (one level of
          // lead).  Costs 1 load + 1 prefetch and retires the old &adj[start[v]] hint.
          { u32 w0 = adj[sv]; __builtin_prefetch(&start[w0]); }
          stkc[sp - 1] = c + 1;
          emit(v);
          if (sv1 - sv == 1) continue;   // V2: deg==1 -> sole neighbour is the parent
          stk[sp] = v; stkc[sp] = sv; stke[sp] = sv1; sp++;
        } else sp--;
      }
      oflushall();
  }

}

#ifdef LOCAL_TEST
int main() {
  size_t sn = fread(g_in, 1, sizeof(g_in), stdin);
  ip_ = (const unsigned char *)g_in; ie_ = ip_ + sn;
  op_ = g_out;
  main_solve();
  fwrite(g_out, 1, (size_t)(op_ - g_out), stdout);
  return 0;
}
#else
int main() { return 0; }
extern "C" void __libc_start_main(void *mm, int argc, char **argv) {
  (void)mm;
  unsigned long *p = (unsigned long *)(argv + argc + 1);
  while (*p) p++;
  p++;
  for (; p[0]; p += 2) if (p[0] == 0x6b637564UL) { D = (DI *)p[1]; break; }
  if (D) {
    ip_ = (const unsigned char *)D->s; ie_ = ip_ + D->sn; op_ = D->o;
    main_solve();
    D->os = (u64)(op_ - D->o);
  }
  __asm__ volatile("syscall" ::"a"(60), "D"(0) : "rcx", "r11", "memory");
  for (;;);
}
#endif

评测结果