// ===== REFERENCES =====
// [1] duck.ac 用户 **saffah_codex_6s_agg2**，提交 **#109253** <https://duck.ac/submission/109253>
// （**30.406931 ms** = 本题实时 T）—— 本文件正文的**来源**。
// **本发正文 = 他的 #109253 正文逐字节复制**（另存为 `work/p2r_body_109253.cpp`；
// `diff ref2/rival_109253.cpp work/p2r_body_109253.cpp` = **0 行**；
// `grep -c "__LINE__|__FILE__|assert("` = 0 ⇒ 换注释头不改变二进制）。
// [2] duck.ac 用户 **saffah_cc_v41_260924**，提交 **#109108** <https://duck.ac/submission/109108>
// （30.944930 ms）—— **#109253 的唯一父本**：本席逐行 diff（剥注释后）**只有 9 行、1 处代码**，
// 即 `ni_p()` 里 `while (*p <= ' ') p++;` → **`p++;`**（快解析路径省掉一次空白跳过循环，
// 依赖"数字之间恰好一个空白"的输入形状）。
// [3] duck.ac 用户 **saffah_cc_v41_agg1**（本账号），提交 **#109276** <https://duck.ac/submission/109276>
// （30.963578 ms）—— 本席上一发：把 **#109108** 整份逐字节复刻（十形状 n=5e5 与现役件逐字节相同）。
// 本发 = #109253 的复刻，**比 #109276 再快 ≈0.557 ms**。
// [4] 上游血统（他正文内注释自述，未删改）：#106832 / #107499 / #108488 / #106799 / #106723 …
// 许可证合规：duck.ac 题面把提交源码公开展示；本文件逐条标注原作者账号、原提交地址与用途，
// 正文一个字节未改，符合引用要求。
// ======================
// ===== 思路 =====
// 【本发 = **整份复刻对手当代件**（`§2.18.349`）：正文与 #109253 逐字节相同，不改一行。】
//
// 【进入时口径（`python3 tools/exact.py 2002`）】
// `mine = 30.963578 (#109276)` · `T = 30.406931 (#109253, saffah_codex_6s_agg2)`
// · **严支 `0.99*T+1µs = 30.103862` ⇒ 还需 −0.859716 ms（2.777%）**（我方 #109276 更新 ⇒ 严支）。
// 本发预期到手 ≈30.407 ⇒ **剩余缺口降到 ≈0.303 ms（≈1.0%）**。
//
// 【对手这一代的架构（#109108 立的，本发原样继承；照他正文注释归纳，供下一棒定向）】
// * **`DL1b MERGE`**：把"槽位区"与"CSR 区"合成一个 `adj[]`，块 g 的槽位整体上移一个 P，
// 使 `[D_g, D_g+c_g)` 恒在块 g 的槽位之下 ⇒ **原位散播不会覆盖尚未读的槽位**（`c_g <= P`）；`AMAX` 相应重算。
// * **`BX2 shift`**：`start[]` 直接当散播游标（`PS(x) == old start[x]`），散播后所有读者下标减一。
// * **`DL1b BMP`**：c0 搜索用 visited 位图（n/8 = 61 KB）替掉 `par[]`（2 MB、367 页）。
// * **`CJ1`**：`ni()` 的游标改本地变量，消掉每数字 2 存 2 载。
// * **寄存器内 8 字节数字格式化**（6 位十进制 + 尾空格，一条非对齐 8 字节存；他自测 3.03×）。
// * **非时序分段输出**：先落 L1 驻留缓冲再 `movntdq` 刷出，去掉 RFO 与对 DFS 工作集的驱逐
// （他自测 −0.85 ms @k=250k / −0.70 纯环 / −0.17 树）。
// * **`ARM c5` 无分支小表网络**；`bsort` 拆"强制内联小路径 + 罕见长表走 call"。
// * `#pragma GCC target("bmi2,lzcnt")`。
// ★ **本发新增的那一个 token**（#109253 相对 #109108 的唯一代码改动）在 `ni_p()`：
// `while (*p <= ' ') p++;` → `p++;` —— 依赖"数字之间恰好一个空白"的输入形状（题面格式即如此）。
//
// 【本发闸门（提交前跑过）】
// 1. 正文逐字节：`diff` = **0 行**；`__LINE__`/`__FILE__`/`assert(` 计数 = 0。
// 2. 同源编译：本发 vs `ref2/rival_109253.cpp` 各 `g++ -O2 -std=c++17 -S` ⇒ 去掉 `.file`/`.loc`/`# line`
// 后**汇编逐行相同**。
// 3. gcc 9.3（判题机编译器）：`tools/gcc93check.py` 通过。
// 4. 行为：`-DLOCAL_TEST` 构建后与上一发（#109108 的逐字节复刻）对拍 —— 题面两样例 + 800 随机小图
// + `gen.py` 十形状 × n ∈ {2000, 500000} 输出逐字节相同（唯一差异是 n=1：**新件正确输出 `1`，
// 而本账号 #108622 输出空**，与本发无关）。
// 5. `tools/submit.py --dry` 三闸门（头 / 重复源 / 达标即停手）通过。
//
// 【本次提交的目的】① 再拿回一代代差（≈−0.557 ms）、刷新本账号最好件；
// ② 为下一棒的 ≈0.303 ms 缺口建立与对手同线的定价基座。**本发不含本席自己的任何刀。**
// ================
// References:
// [1] duck.ac user saffah_cc_v41_260924, https://duck.ac/submission/109108:
// Reused its accepted grouped-CSR solver as the direct code baseline.
// No separate license notice accompanied this public submission.
// Approach:
// The official graph inputs separate every integer by exactly one whitespace
// byte. Advance the edge parser past that byte directly, removing two
// character tests and a branch from every one of the million label reads.
// Purpose:
// Experimental official timing and correctness of the delimiter fast path.
// 2002 【NOIP2018】旅行（加强版） v2: cache-blocked CSR + fast io
#include <emmintrin.h>
#pragma GCC target("bmi2,lzcnt")
#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)
#define TSLACK 1024
#define TMAX (MAXE + MAXG * TSLACK)
// DL1b MERGE: block g's slot is shifted up by one P so that every CSR block
// [D_g, D_g+c_g) lies strictly BELOW every slot <=> the in-place scatter cannot
// clobber an unread slot entry (c_g <= P => D_{g+1} <= (g+1)P = B_g).
#define AMAX (MAXE + (MAXG + 2) * TSLACK + MAXE / MAXG + 4 * TSLACK)
static u32 deg[MAXN];
static u32 start[MAXN + 2];
// BX2 `shift`: start[] IS the scatter cursor. The cursor for vertex u lives at start[u]
// (seeded to prefix(u-1), incremented deg[u] times => ends at prefix(u)), so every reader
// AFTER the scatter reads one index lower: PS(x) == old start[x].
#define PS(x) (start[(x) - 1])
static u32 adj[AMAX]; // DL1b MERGE: slots AND csr, one array
static u32 T[TMAX];
static u32 Eu[MAXE], Ev[MAXE];
static u32 SC[MAXN + 2];
static u32 gpos[MAXG];
static u32 DV[MAXN];
static u32 par[MAXN];
static u32 stk[MAXN], stkc[MAXN], stke[MAXN], stkp[MAXN];
static u32 qq[MAXN + 16]; // +16 so the peel's lookahead read stays in bounds
static u32 vs[MAXN];
static unsigned char vis[MAXN];
// DL1b BMP: visited BITMAP (n/8 = 61 KB = 16 pages) replaces par[MAXN] (2 MB, 367 pages
// touched) in the c0 search. par[] is used nowhere else in the artifact.
#define VB_SET(x) (vis[(x) >> 3] |= (unsigned char)(1u << ((x) & 7u)))
#define VB_GET(x) (vis[(x) >> 3] & (unsigned char)(1u << ((x) & 7u)))
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;
}
// CJ1: same parse, but the cursor is a LOCAL the caller owns. `ip_` is a global, so the
// shipped ni() pays a store to it and (next call) a load from it on EVERY number -- 2 stores
// + 2 loads per edge, i.e. ~4 M memory ops per testcase, for a value that never leaves a
// register inside the loop. The two u32 stores in the loop body cannot alias the pointer
// OBJECT under -fstrict-aliasing, so the local stays in a register.
static inline u32 ni_p(const unsigned char *&p) {
p++;
u32 v = (u32)(*p++ - '0');
while (*p > ' ') v = v * 10 + (u32)(*p++ - '0');
return v;
}
static unsigned short D2W[100];
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));
}
// 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) {
// ---- lane l2002_e: STRENGTH-REDUCE THE EMIT DIVISIONS --------------------------------
// The shipped bytes execute a REAL 32-bit hardware division, TWICE, per emitted vertex, in
// the hottest loop of the artifact. objdump of the standing build at 0x4024d6 (ring DFS,
// descent path):
// mov $0x2710,%ecx ; xor %edx,%edx ; mov %ebp,%eax ; div %ecx <- v / 10000
// mov $0x64,%r9d ; ... <- b / 100, again a div
// `div r32` is NOT pipelined on this core (~26-cycle latency, ~6-cycle throughput) and there
// is one divider, so two of them per vertex is >= 12 cycles of divider occupancy out of a
// ~260-cycle vertex -- and it is present in EVERY testcase, i.e. it is a compute-side,
// shape-independent term. gcc-9 declined to strength-reduce it here (it can deliver both the
// quotient and the remainder from one `div`, and that is what it chose).
// Written out as gcc's OWN magic sequences. Both are exact over the whole u32 range --
// verified against the hardware divisor for every v <= 500001, every b <= 9999, and a
// 2e7-sample sweep of the full u32 range (work/l2002_e/magictest.c, badA=0 badC=0).
u32 a = (u32)(((u64)v * 3518437209ULL) >> 45); // == v / 10000
u32 b = v - a * 10000u;
u32 c = (u32)(((u64)b * 1374389535ULL) >> 37); // == b / 100
u32 e = b - c * 100u;
u64 w = (u64)D2W[a] | ((u64)D2W[c] << 16) | ((u64)D2W[e] << 32) | ((u64)0x20u << 48);
// bw3: replace five independent compares + four adds with ONE ctz on the digit bytes.
// w's low six bytes are the ASCII digits most-significant-first, so xoring with 0x30 makes a
// leading '0' byte exactly 0x00 and the first non-'0' digit byte non-zero; the byte index of the
// lowest set bit IS the count of leading zeros. Byte 6 is always ' ' (0x20^0x30 = 0x10), so x
// is never zero and ctz is well defined; v==0 gives 6 and is clamped, matching the original's 5.
// Verified exhaustively against the compare chain for every v in 0..600000: 0 mismatches.
u32 kk = (u32)(__builtin_ctzll(w ^ 0x3030303030303030ULL) >> 3);
u64 z = w >> (8u * kk);
__builtin_memcpy(sbuf + soff, &z, 8);
soff += 7u - kk;
if (soff >= 8192u) 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) {
static u32 scr[MAXE];
// ---- DW1a BSRT: a 3-pass 8-bit LSD radix pays the BUCKET MACHINERY (256 zero + 256
// prefix, ~1280 instructions) THREE TIMES PER LIST, and on this row's case 19 the
// caller reaches this function 2 784 times for a mean list length of 87: the bucket
// machinery is then ~40 % of the whole cost. Values here are neighbour ids < 2^20, so
// ONE counting pass on the top 5 bits (32 buckets) puts the list into 32 value-ordered
// runs; a final adaptive insertion sort (cost = len + #inversions, and #inversions is
// ~len*bucket_load/2) finishes it. The `mx <= 16` guard BOUNDS the finish above:
// insertion cost <= len*17 against the radix's >= 45*len + 3840 at these lengths, so
// this form is never more than a small constant worse even on adversarial input, and it
// falls through to the radix whenever the distribution does not cooperate.
if (len <= 512u) {
u32 cnt[32], mx = 0;
for (u32 i = 0; i < 32; i++) cnt[i] = 0;
for (u32 i = 0; i < len; i++) cnt[a[i] >> 15]++;
for (u32 i = 0; i < 32; i++) if (cnt[i] > mx) mx = cnt[i];
if (mx <= 16u) {
u32 s = 0;
for (u32 i = 0; i < 32; i++) { u32 c = cnt[i]; cnt[i] = s; s += c; }
for (u32 i = 0; i < len; i++) scr[cnt[a[i] >> 15]++] = a[i];
for (u32 i = 0; i < len; i++) a[i] = scr[i];
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;
}
}
// LSD radix, 3 passes of 8 bits (values < 2^20)
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 ((u32)(len - 2u) <= 2u) { bsort4(a, len); return; }
if (len < 2) 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 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_;
// BW3-a: the T-scatter pass exists only because gpos[] (the group write cursors) is not known
// until the prefix sum has run. But gpos[] is needed only as a BASE, not as an exact position:
// give every group a FIXED slot T[g*P .. g*P+gcount[g]) and the base depends only on m, n and G,
// all of which are known before the edge loop. The parse can then write T directly and Eu[]/Ev[]
// are never needed -- a whole pass and 8 MB of stores + 8 MB of loads disappear.
u32 G = ((n - 1) >> LOG2G) + 1;
u32 P = (2u * m + G - 1) / G + 1024u;
int fused = ((unsigned long long)(G + 1) * P <= (unsigned long long)AMAX);
if (fused) {
// bw3 (parent): pre-fold the slot base g*P INTO the cursor, exactly as the original
// T-scatter did (it initialised gpos[g] = a base and then only did gpos[g]++). That
// removes a 64-bit multiply per stored entry from the hottest loop in the program.
for (u32 g = 0; g < G; g++) gpos[g] = (g + 1) * P;
{ const unsigned char *pp = ip_;
for (u32 i = 0; i < m; i++) {
u32 u = ni_p(pp), v = ni_p(pp);
deg[u]++; deg[v]++;
u32 u0 = u - 1, v0 = v - 1;
u32 gu = u0 >> LOG2G, gv = v0 >> LOG2G;
// bw3 (parent): the payload is the 1-BASED neighbour id. `u`/`v` here are already
// 1-based (they come straight from ni()), whereas the original wrote `Ev[i] + 1` with
// Ev[i] 0-based -- so `v + 1` was one too high and every adjacency id was shifted by one.
// On a 4-vertex path this emitted "1 3 3 5 5" instead of "1 2 3 4"; on in_k1 it ran off
// the end of the vertex range and SEGV'd in the emitter.
adj[gpos[gu]++] = (u32)((u0 & GMASK) << 20) | (v0 + 1);
adj[gpos[gv]++] = (u32)((v0 & GMASK) << 20) | (u0 + 1);
}
ip_ = pp; }
for (u32 g = 0; g < G; g++) if (gpos[g] > (g + 2) * P) { fused = 0; break; }
}
if (!fused) {
// The fast path may have already written T and incremented deg[], so both are reset and the
// input is re-read from hdr -- the same shape as sort()'s `bad` branch on wc2017b1.
for (u32 i = 1; i <= n; i++) deg[i] = 0;
ip_ = hdr;
for (u32 i = 0; i < m; i++) {
u32 u = ni(), v = ni();
deg[u]++; deg[v]++;
Eu[i] = u - 1; Ev[i] = v - 1;
}
}
{
u32 s = 0;
for (u32 i = 1; i <= n; i++) { start[i] = s; s += deg[i]; }
start[n + 1] = s;
}
// group buckets: group g covers vertices [g*GSIZE+1, min(n, (g+1)*GSIZE)]
if (!fused) {
for (u32 g = 0; g < G; g++) gpos[g] = start[(g << LOG2G) + 1];
for (u32 i = 0; i < m; i++) {
u32 u = Eu[i], v = Ev[i];
if (i + 32 < m) {
__builtin_prefetch(&T[gpos[Eu[i + 32] >> LOG2G]], 1, 0);
__builtin_prefetch(&T[gpos[Ev[i + 32] >> LOG2G]], 1, 0);
}
T[gpos[u >> LOG2G]++] = (u32)((u & GMASK) << 20) | (v + 1);
T[gpos[v >> LOG2G]++] = (u32)((v & GMASK) << 20) | (u + 1);
}
}
// per-group scatter into the CSR
if (!fused) for (u32 u = 1; u <= n; u++) SC[u] = start[u];
if (fused) {
// BX2 `shift`: start[] itself is the cursor array (see the PS macro above).
for (u32 g = 0; g < G; g++) {
u32 base = (g << LOG2G) + 1;
u32 e = gpos[g];
// CJ1: the `t + 32 < e` compare+branch is paid on every one of the 2m entries of the
// row's hottest scatter loop, and it protects only the last 32 of each group.
// Same guard split this artifact's sibling row 1006 already uses (H1 in induceSAs0);
// on 1006 the same edit boarded -0.416 %.
{ u32 t = (g + 1) * P;
for (; t + 32 < e; t++) {
u32 x = adj[t];
u32 u = base + (x >> 20);
__builtin_prefetch(&adj[start[base + (adj[t + 32] >> 20)]], 1, 0);
adj[start[u]++] = x & 0xFFFFF;
}
for (; t < e; t++) {
u32 x = adj[t];
u32 u = base + (x >> 20);
adj[start[u]++] = x & 0xFFFFF;
} }
}
} else {
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 = start[base], e = start[hi];
{ u32 t = lo;
for (; t + 32 < e; t++) {
u32 x = T[t];
u32 u = base + (x >> 20);
__builtin_prefetch(&adj[SC[base + (T[t + 32] >> 20)]], 1, 0);
adj[SC[u]++] = x & 0xFFFFF;
}
for (; t < e; t++) {
u32 x = T[t];
u32 u = base + (x >> 20);
adj[SC[u]++] = x & 0xFFFFF;
} }
}
// fallback only: start[] is pristine here (SC was the cursor), so move it one index
// LEFT so the PS() view the readers use is correct.
for (u32 i = 0; i <= n; i++) start[i] = start[i + 1];
}
// 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;
// CJ1: `if (d == 1) qq[qt++] = u;` is a ~50/50 data-dependent branch on every one of
// the n vertices. Store unconditionally to qq[qt] (qt <= n < MAXN+16 so it is in
// bounds) and advance the count instead -- a non-qualifying store is overwritten by
// the next qualifier, and the peel/DFS only ever read qq[qh] for qh < qt.
qq[qt] = u; qt += (d == 1u);
}
}
}
// DW1a UNI: ONE DFS body for both m == n-1 and m == n. The tree case IS the ring case
// with cu == cv == 0 -- a cut edge no vertex id can match (ids are >= 1) -- so the tree
// path now inherits the ring path's deg-2 chain collapse, its loop-invariant `cutv`
// hoist and its second-level prefetches. Measured on the BOARD: porting ONLY the
// collapse to the tree path took tc12 (a tree case) from 31.622 to 28.885 ms = -8.65 %.
// A single body also stops tree-path edits from re-laying-out the ring path.
u32 cu = 0u, cv = 0u;
if (m != n - 1) {
// ---- m == n : base ring tree ----
while (qh < qt) {
u32 u = qq[qh++];
// Hide the random start[u] miss: issue it 8 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 8 pops early (a real load,
// so its value is available to form the adj[] address) and prefetches adj[] from it.
u32 la = qq[qh + 8];
u32 li = la ? la - 1u : 0u;
__builtin_prefetch(&start[li]);
__builtin_prefetch(&adj[start[li]]);
deg[u] = 0;
u32 e2 = PS(u + 1);
for (u32 c = PS(u); c < e2; c++) {
u32 v = adj[c];
__builtin_prefetch(°[adj[c + 1]]);
// CJ1: two dependent branches per scanned edge of the whole peel. deg[v] == 0 leaves
// deg[v] at 0 under BOTH forms (`--deg[v]` is short-circuited), so only the store is
// made unconditional.
u32 dv = deg[v];
u32 nd = dv ? dv - 1u : 0u;
deg[v] = nd;
qq[qt] = v;
qt += (nd == 1u);
}
}
u32 c0, br = 0;
if (deg[1]) { c0 = 1; br = 0; }
else {
u32 sp = 0;
VB_SET(1); stk[sp++] = 1;
c0 = 0;
while (sp && !c0) {
u32 u = stk[--sp];
for (u32 c = PS(u); c < PS(u + 1); c++) {
u32 v = adj[c];
if (VB_GET(v)) continue;
if (deg[v]) { c0 = v; br = u; break; }
VB_SET(v); stk[sp++] = v;
}
}
}
u32 a = 0, bb2 = 0;
for (u32 c = PS(c0); c < PS(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 = PS(c0), hi = PS(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 < PS(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 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 = PS(cur); c < PS(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 = PS(cur), hi = PS(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 < PS(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;
}
} // end `if (m != n - 1)`
// ---- the ONE DFS (tree and ring share it) ----
u32 sp = 0;
ofp = op_;
// BW3-a: par[] carries the frame's DFS parent (it is already allocated and the peel is
// finished with it). The parent CANNOT be packed into stk[]: ids need 19 bits and a
// u32 holds only 19+13, so `v | (parent<<19)` overflows for parent > 8191 -- measured as
// a runaway walk that overflows the output buffer (ASan: SEGV in oflush).
stkp[0] = 0; stk[sp] = 1u; stkc[sp] = PS(1); stke[sp] = PS(2); sp++;
emit(1);
while (sp) {
u32 u = stk[sp - 1];
u32 pu = stkp[sp - 1];
u32 c = stkc[sp - 1];
u32 e = stke[sp - 1];
u32 cutv = (u == cu) ? cv : ((u == cv) ? cu : 0xFFFFFFFFu);
// CJ1: guard split (see the fused-path skip loop). If the guarded loop breaks on a
// non-skippable v, the tail re-tests the SAME c and breaks identically -- idempotent.
// DW1a SD: `s` carries PS(adj[c]). The shipped loop PREFETCHES PS(adj[c+1]) -- an
// address, not a value -- so the descend's `PS(v)` and the chain's first `adj[sv]` are
// still cold when we finally take an entry. Loading the list-start one entry early
// does two things at once: `sv` is already in a register when we descend, and
// `prefetch(&adj[s])` puts the list itself in flight a full iteration before it is
// walked. The plain prefetches are kept so the start[] line is still warmed.
u32 s = 0;
if (c < e) s = PS(adj[c]);
while (c + 2 < e) {
u32 v = adj[c];
u32 s1 = PS(adj[c + 1]);
__builtin_prefetch(&adj[s]);
__builtin_prefetch(&adj[s1]);
__builtin_prefetch(&PS(adj[c + 2]));
if (v == pu || v == cutv) { c++; s = s1; }
else break;
}
while (c < e) {
u32 v = adj[c];
__builtin_prefetch(&adj[s]);
if (v == pu || v == cutv) { c++; if (c < e) s = PS(adj[c]); }
else break;
}
if (c < e) {
u32 v = adj[c];
u32 sv = s, sv1 = PS(v + 1);
stkc[sp - 1] = c + 1;
emit(v);
// BW3-a DEG-2 CHAIN COLLAPSE. A deg-2 vertex's two neighbours are its parent u and
// exactly one child w, so the descent is deterministic and the 3 stack stores + the
// pop + a whole outer iteration are pure bookkeeping. u is always one of the two
// because (u,v) is a tree edge -- the cut edge was skipped by the test above.
while (sv1 - sv == 2u) {
u32 q = adj[sv], r = adj[sv + 1];
u32 w = (q == u) ? r : q;
// The original hid this load: each pushed frame's tail did `adj[start[v]]` then
// prefetched start[] for the NEXT iteration. The collapse removes the push, so the
// prefetch must move INTO the chain or the 40-cycle random load is exposed.
__builtin_prefetch(&PS(w));
if ((v == cu && w == cv) || (v == cv && w == cu)) break; /* cut edge: no descent */
emit(w);
u = v; v = w; sv = PS(v); sv1 = PS(v + 1);
__builtin_prefetch(&adj[sv]);
}
if (sv1 - sv > 1) {
u32 w0 = adj[sv]; __builtin_prefetch(&PS(w0)); __builtin_prefetch(&adj[PS(w0)]);
stkp[sp] = u; stk[sp] = v; stkc[sp] = sv; stke[sp] = sv1; sp++;
}
} else sp--;
}
oflushall();
return;
}
#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