// 2002 【NOIP2018】旅行（加强版） v2: cache-blocked CSR + fast io
#include <emmintrin.h>
#pragma GCC target("bmi2,lzcnt")
#pragma GCC optimize("O3","unroll-loops","no-crossjumping")
#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) {
// DZ1 NSEP: the leading `while (*p <= ' ') p++` has a CONSTANT trip count of 1 in this
// input's format, but it costs a load, a compare and a branch on every number (1M
// numbers per case). Verified on the max-size fixture: 500001 spaces, 500001 newlines,
// ZERO CR, ZERO TAB, ZERO double-space, and every one of the 500001 edge lines is
// exactly `u v`. ni_p now leaves p ON the separator and the caller advances by one.
// DZ1 PAIR: the Horner chain v = v*10 + d is ~2 cycles per DIGIT (two LEAs) and is
// loop-carried, so a 6-digit number costs ~12 cycles of chain. Two digits per step put
// the pair value (d0*10 + d1) OFF the chain and make the carried step v*100, i.e. ~2
// cycles per TWO digits. Exact for every digit count: pairing consumes digits only
// while two remain, and the tail handles the odd one.
u32 v = (u32)(*p++ - '0');
while (p[0] > ' ' && p[1] > ' ') {
v = v * 100u + (u32)((*p - '0') * 10u + (p[1] - '0'));
p += 2;
}
if (*p > ' ') v = v * 10u + (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_ + 1;
for (u32 i = 0; i < m; i++) {
u32 u = ni_p(pp); ++pp;
u32 v = ni_p(pp); ++pp;
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) {
// DZ1 DGHIST: the degree RMWs used to live in the parse, scattered over the whole
// 2 MB deg[] (490 pages) at one random address per edge. They are moved here,
// where for group g the target is confined to deg[(g<<12)+1 .. (g<<12)+4096)
// = ONE 16 KB window that is L1-resident for the whole group. The block is
// walked sequentially and each entry's top 12 bits ARE the vertex's local id
// ((u-1) & GMASK), so base + (adj[t]>>20) == u exactly.
for (u32 g = 0; g < G; g++) {
u32 dbase = (g << LOG2G) + 1, de = gpos[g];
for (u32 t = (g + 1) * P; t < de; t++) deg[dbase + (adj[t] >> 20)]++;
}
}
}
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