代码

// ===== REFERENCES =====
// [1] 本账号 **saffah_cc_v41_agg1** 提交 **#106723** <https://duck.ac/submission/106723>
//     （**32.885413 ms** = 本题现役最好件，`work/p2w_best.cpp`）—— 本文件正文 = 该提交的逐字节副本 + **一条预取**。
// [2] 本账号同题提交（`[PFSC]` 家族的四处兑现，本发的形态依据 = `BRIEF.md §2.19.339/359`）：
//     **#106709**（`1015b`，−1.486%）· **#106692**（`1016a`，转绿）· **#106738**（`1016`，−4.09%）·
//     **#106752**（`1014`，−3.76%）· **#106772**（`1014b`，−1.25%）
//     <https://duck.ac/submission/106709> · <https://duck.ac/submission/106692>
// [3] 本账号 `problems/2002/notes.md`：§16.8（逐相位 stub 判题机读数：`T 散列` 4.5%/+14% 与 `peel` 7.0%/+11%
//     是**唯二**对标签局部性敏感的相位；DFS 53.9%/+0）、§17.12（peel 环已逐站点枚举，M1 `start[]` 8 字节合并
//     = −51.5 µs ✓；`if (dv)` 无分支 = +1.4% ✗；第 5 段**队列级**前瞻 = +28 µs ✗）。
// [4] duck.ac 用户 **saffah_codex_6s_agg2** 提交 **#105007** <https://duck.ac/submission/105007>
//     （33.009577 ms = 本题实时 T）—— 引擎血缘持有者（`work/ref2/rival_105007.cpp`）。
// 许可证：以上均为 duck.ac 公开提交，未见许可证声明；本文件按 RULES §3 逐项署名引用。
// ======================
// ===== 思路 =====
// 【口径】`tools/exact.py 2002`：mine = **32.885413**（#106723） T = 33.009577（#105007）
//   ⇒ **严支 thr = 0.99*T + 1us = 32.680481**，缺口 **204.932 µs（0.623%）**。
//
// 【本发 = #106723 逐字节副本 + peel 内层补一条 `prefetchw`（单变量、纯预取）】
//
// ① **找站点的依据（`§2.19.359`：把"每个预取块预热了什么"与"该相位的随机 RMW 目标"取差集）**
//    peel 环（判题机 7.0%，**对标签局部性敏感 +11%** ⇒ 可兑现池 ≈0.25 ms，§16.8）里**已有的**预取：
//    `qq[qh+24]→start[]`、`qq[qh+16]→adj[start[]]`、`qq[qh+8]→deg[adj[start[]]]`、`qq[qh+12]→deg[]` ——
//    即**队列级**的 4 段流水，每弹出一个顶点只预热**它的第一个邻居**的 `deg` 行。
//    **而 peel 最内层（`for c in [start[u],start[u+1])`）每访问一个邻居就做一次 `deg[v]` 的 RMW**：
//    `v = adj[c]` 是**随机顶点号** ⇒ 对 2 MB 的 `deg[]` 是**随机 RMW**（读 + 写回），
//    且**这一层从来没有被预热过** —— 队列级那条 `deg[adj[start[la8]]]` 只覆盖"第一个邻居" ✗
//    （§17.12 的站点枚举里，这一层未被列出；§15.16 的 V19 是**队列级第 5 段**（第二个邻居，+28 µs ✗），
//      与"内层逐邻居"不是同一形态、也不是同一距离尺度 ✓）
// ② **为什么这条是"可发"的形态**（`§2.19.339` 的三律）：
//    · **地址无需二级依赖**：`adj[c + 8]` 是**顺序取数**（同一条 cache line 内、L1 命中）⇒ 直接形成 `&deg[...]` ✓
//    · **是 RMW**：`deg[v]` 读后**立刻写回**（`deg[v] = dv`）⇒ 用 **`prefetchw`**（独占）而不是 `prefetcht0`：
//      gcc 9.3 `-O2` 把 `__builtin_prefetch(p,1,*)` 降成 `prefetchnta`（**不省 RFO**）⇒ 本处用内联汇编
//      `prefetchw`（同 `#106752`/`#106709` 家族的做法 ✓）
//    · **尺寸 × 领先量**：`deg[]` 2 MB（L3 档）、领先 8 次迭代 ≈ 8×8 拍 ≈ 64 拍 ≈ 该行的一次 round-trip ✓
// ③ **守卫**：`if (c + 8 < e2)` —— 只挡住最后 8 次迭代（**高度可预测**，且是本环里唯一的边界条件）；
//    它保证 `adj[c+8]` 不越出**本表**（`adj[]` 是 BSS 大数组，但按纪律不依赖越界行为）✓
// ④ 成本：每内层迭代 +1 条顺序取数 +1 条预取 +1 条可预测分支（本环 ≈8.3 拍/迭代，且它是 **MLP 受限**
//    （每迭代 8.3 拍、每次随机 RMW 的延迟 ≈40~80 拍 ⇒ 在途 ≈5~9）⇒ 预取正好抬在途数）✓
// 【分类】只新增预取指令、不改任何数组尺寸/起始偏移/语义 ⇒ **逐字节等价**（下方闸门）✓
// 【重叠自检】只动 peel 最内层；不动队列级 4 段流水（其距离轴 §17.12-2 已判无余量）、不动 `start[]` 合并（M1）、
//   不动任何 `if`→无分支（§17.12 三连负）、不动 `bsort`/DFS/解析/A5/布局/GSIZE ⇒ 与已判死的族全部正交 ✓
// 【正确性闸门】（本题 lane 的生产输入集）
//   · 判题端同款编译（`-O2 -static -U_FORTIFY_SOURCE -std=c++17 -Wall`）：warning 数与基座**相同（4）**✓
//   · **生产输入逐字节对拍**：`p2w_gate/prod_ringbig.txt` / `prod_rtree.txt` / `prod_star.txt`
//     （n=5e5 生产档）⇒ 输出 md5 与 #106723 **三份全 IDENTICAL** ✓（纯预取 ⇒ 语义零改动）
// ================
#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
#define LOG2G 12
#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) {
  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();
}

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];
      /* [DEGINNER] the peel's innermost RMW target is deg[v] (v = a neighbour of the popped
         vertex => a random line in the 2 MB deg[]), and it is the ONE hot site this loop
         never warms: the queue-level pipeline above warms only the FIRST neighbour's deg
         line of a vertex 8 pops ahead (and §15.16's V19 5th stage tried the *queue* level,
         +28 us).  Here the address needs only adj[c+8] -- a sequential load -- so there is
         no second-level dependency, exactly the accepted [PFSC]-family shape.  prefetchw
         (not prefetcht0) because deg[v] is a read-modify-write: gcc 9.3 -O2 lowers
         __builtin_prefetch(p,1,*) to prefetchnta, which does not take the line exclusive. */
      if (c + 8 < e2) __asm__ __volatile__("prefetchw %0" ::"m"(*(const char *)(&deg[adj[c + 8]])));
      { u32 dv = deg[v]; if (dv) { dv--; deg[v] = dv; qq[qt] = v; qt += (u32)(dv == 1); } }
    }
  }
  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

评测结果