代码

/*
References:
- duck.ac user saffah_cc_v41_agg1, https://duck.ac/submission/106832: copied its publicly visible accepted 2002 graph solver and retained its original source citation block; no separate license notice appeared.
- duck.ac user saffah_codex_6s_agg2, https://duck.ac/submission/107499: used our fastest accepted A5-prefetch source as the direct base; our own source has no separate license notice.
Approach:
- For each 256-label block, save its first adjacency offset. If every block spans at most 4094 edges, encode each DFS edge in 4 bytes: 19-bit label, 12-bit local start offset (4095 means leaf), and one last-neighbour flag. Otherwise retain the original five-byte DFS path. The four-byte records fit in 4 MB and use aligned loads.
Purpose:
- Experimentally test whether a lossless, cache-friendlier DFS record reduces 2002's official runtime while preserving its output.
*/
/*
References:
- saffah_cc_v41_agg1, https://duck.ac/submission/106832: copied the publicly visible accepted 2002 graph solver, retaining its original source credit block. No separate license notice was shown.
- saffah_codex_6s_agg2, https://duck.ac/submission/107468: consulted the prior A5 build prefetch experiment where relevant.
Approach:
- Issue the existing child A5 prefetch before formatting and emitting the child vertex in both A5 DFS branches.
Purpose:
- Compare total official Try It runtime and output hash across representative full-size graph shapes before judged submission.
*/
// ===== 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];
  u32 A4B_[MAXE + 16];
};
static union Y2BU YU;
#define T   YU.s.TT
#define Eu  YU.s.EEu
#define Ev  YU.s.EEv
#define A5B YU.A5B_
#define A4B YU.A4B_
static u32 gA4Base[(MAXN + 255) / 256 + 2];
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;   // 父帧游标；哨兵 = 该表已空
      if (sv != 0xFFFFFu) __builtin_prefetch(A5B + (size_t)sv * 5);
      emit(v);
      // V2: deg[v]==1 <=> v 自己表的首条目就是最后一条（同线一次读，取代 sv1-sv==1）
      if (sv == 0xFFFFFu) continue;   // [y3] deg-1 child: no 2nd load
      stk[sp] = v; stkc[sp] = sv; sp++;
    } else sp--;
  }
  oflushall();
}

// A4 DFS: block-relative start offsets shrink the complete edge table to 4 MB.
static __attribute__((noinline)) void y2b_a4_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];
    u32 d=(start[w+1]==st+1)?4095u:(st-gA4Base[(w-1)>>8]);
    A4B[cc]=w|(d<<19);
  }
  for(u32 u=1;u<=n;u++) if(start[u+1]>start[u])
    A4B[start[u+1]-1] |= 0x80000000u;
  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], c=stkc[sp-1];
    u32 pu=sp>=2?stk[sp-2]:0;
    u32 v=0, dv=0,last=0;
    for(;;) {
      if(c==0xFFFFFFFFu)break;
      u32 z=A4B[c];
      u32 x=z&524287u;
      last=z>>31;
      if(!(x==pu||(u==cu&&x==cv)||(u==cv&&x==cu))) {
        v=x;dv=(z>>19)&4095u;break;
      }
      if(last){c=0xFFFFFFFFu;break;}
      c++;
    }
    if(v) {
      stkc[sp-1]=last?0xFFFFFFFFu:c+1;
      u32 sv=(dv==4095u)?0xFFFFFFFFu:(gA4Base[(v-1)>>8]+dv);
      if(dv!=4095u)__builtin_prefetch(A4B+sv);
      emit(v);
      if(dv==4095u)continue;
      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;   // 父帧游标；哨兵 = 该表已空
          if (sv != 0xFFFFFu) __builtin_prefetch(A5B + (size_t)sv * 5);
          emit(v);
          // V2: deg[v]==1 <=> v 自己表的首条目就是最后一条（同线一次读，取代 sv1-sv==1）
          if (sv == 0xFFFFFu) continue;   // [y3] deg-1 child: no 2nd load
          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)) {
    int use4=1;
    for(u32 base=1;base<=n;base+=256){
      u32 end=base+256;if(end>n+1)end=n+1;
      gA4Base[(base-1)>>8]=start[base];
      if(start[end]-start[base]>4094u)use4=0;
    }
    if(use4)y2b_a4_dfs(n,m,cu,cv);
    else 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

评测结果