代码

#ifndef DUCK_FASTIO_H
#define DUCK_FASTIO_H

typedef unsigned long duck_u64;
typedef long duck_i64;

typedef struct {
    duck_u64 abi_version;
    const char *stdin_ptr;
    duck_u64 stdin_size;
    char *stdout_ptr;
    duck_u64 stdout_limit;
    duck_u64 stdout_size;
    char *stderr_ptr;
    duck_u64 stderr_limit;
    duck_u64 stderr_size;
    const char *ib_ptr;
    duck_u64 ib_limit;
    char *ob_ptr;
    duck_u64 ob_limit;
    duck_u64 tsc_frequency;
} __attribute__((packed)) DuckInfo;

static __attribute__((always_inline)) inline DuckInfo *duck_info(long argc, char **argv) {
    char **p = argv + argc + 1;
    while (*p) ++p;
    duck_u64 *aux = (duck_u64 *)(p + 1);
    while (aux[0]) {
        if (aux[0] == 0x6b637564UL) return (DuckInfo *)aux[1];
        aux += 2;
    }
    return (DuckInfo *)0;
}

static __attribute__((always_inline)) inline duck_u64 duck_read_u64(const char **cursor) {
    const char *p = *cursor;
    while ((unsigned char)(*p - '0') > 9) ++p;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return value;
}

static __attribute__((always_inline)) inline duck_i64 duck_read_i64(const char **cursor) {
    const char *p = *cursor;
    while (*p != '-' && (unsigned char)(*p - '0') > 9) ++p;
    int negative = *p == '-';
    p += negative;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return negative ? -(duck_i64)value : (duck_i64)value;
}

static __attribute__((always_inline)) inline char *duck_write_u64(char *out, duck_u64 value) {
    char tmp[24];
    unsigned n = 0;
    do {
        tmp[n++] = (char)('0' + value % 10);
        value /= 10;
    } while (value);
    do *out++ = tmp[--n]; while (n);
    return out;
}

static __attribute__((always_inline)) inline char *duck_write_i64(char *out, duck_i64 value) {
    if (value < 0) {
        *out++ = '-';
        return duck_write_u64(out, (duck_u64)(-value));
    }
    return duck_write_u64(out, (duck_u64)value);
}

static __attribute__((always_inline, noreturn)) inline void duck_exit(void) {
    __asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall" ::: "rax", "rdi", "rcx", "r11", "memory");
    __builtin_unreachable();
}

#endif


typedef unsigned int u32;

enum { MAXN = 500005, MAXE = 1000010 };

static int head[MAXN], link_next[MAXE], link_src[MAXE];
static int degree[MAXN], offset[MAXN + 1], cursor[MAXN];
static int adjacency[MAXE], queue_[MAXN];
static unsigned char in_cycle[MAXN], visited[MAXN];

typedef struct {
    int x;
    int parent;
    int next_after;
    int pos;
    int end;
    int cut_neighbor;
} Frame;
static Frame stack_[MAXN];

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

static __attribute__((always_inline)) inline char *write_u32(char *p, u32 x) {
    if (x >= 10000u) {
        if (x >= 100000u) {
            u32 hi = x / 10000u;
            u32 lo = x - hi * 10000u;
            u32 a = lo / 100u;
            *p++ = (char)('0' + hi / 10u);
            *p++ = (char)('0' + hi % 10u);
            *(unsigned short *)p = *(const unsigned short *)(digit_pairs + 2 * a);
            *(unsigned short *)(p + 2) =
                *(const unsigned short *)(digit_pairs + 2 * (lo - a * 100u));
            return p + 4;
        }
        u32 hi = x / 10000u;
        u32 lo = x - hi * 10000u;
        u32 a = lo / 100u;
        *p++ = (char)('0' + hi);
        *(unsigned short *)p = *(const unsigned short *)(digit_pairs + 2 * a);
        *(unsigned short *)(p + 2) =
            *(const unsigned short *)(digit_pairs + 2 * (lo - a * 100u));
        return p + 4;
    }
    if (x >= 1000u) {
        u32 a = x / 100u;
        *(unsigned short *)p = *(const unsigned short *)(digit_pairs + 2 * a);
        *(unsigned short *)(p + 2) =
            *(const unsigned short *)(digit_pairs + 2 * (x - a * 100u));
        return p + 4;
    }
    if (x >= 100u) {
        u32 a = x / 100u;
        *p++ = (char)('0' + a);
        *(unsigned short *)p =
            *(const unsigned short *)(digit_pairs + 2 * (x - a * 100u));
        return p + 2;
    }
    if (x >= 10u) {
        *(unsigned short *)p = *(const unsigned short *)(digit_pairs + 2 * x);
        return p + 2;
    }
    *p = (char)('0' + x);
    return p + 1;
}

static void run(DuckInfo *info) {
    const char *in = info->stdin_ptr;
    int n = (int)duck_read_u64(&in);
    int m = (int)duck_read_u64(&in);

    for (int i = 0; i < m; ++i) {
        int u = (int)duck_read_u64(&in);
        int v = (int)duck_read_u64(&in);
        int e = i + i;
        link_src[e] = u;
        link_next[e] = head[v];
        head[v] = e + 1;
        link_src[e + 1] = v;
        link_next[e + 1] = head[u];
        head[u] = e + 2;
        ++degree[u];
        ++degree[v];
    }

    for (int u = 1; u <= n; ++u) {
        offset[u + 1] = offset[u] + degree[u];
        cursor[u] = offset[u];
    }
    for (int v = 1; v <= n; ++v) {
        for (int q = head[v]; q; q = link_next[q - 1]) {
            int u = link_src[q - 1];
            adjacency[cursor[u]++] = v;
        }
    }

    if (m == n) {
        int qh = 0, qt = 0;
        for (int u = 1; u <= n; ++u) {
            in_cycle[u] = 1;
            if (degree[u] == 1) queue_[qt++] = u;
        }
        while (qh < qt) {
            int u = queue_[qh++];
            in_cycle[u] = 0;
            for (int p = offset[u]; p < offset[u + 1]; ++p) {
                int v = adjacency[p];
                if (degree[v] > 1 && --degree[v] == 1) queue_[qt++] = v;
            }
            degree[u] = 0;
        }
    }

    char *out = info->stdout_ptr;
    int sp = 0;
    int returned = 0;
    stack_[0] = (Frame){1, 0, n + 1, offset[1], offset[2], 0};
    visited[1] = 1;
    out = write_u32(out, 1);

    while (sp >= 0) {
        Frame *f = &stack_[sp];
        int x = f->x;

        /* Entry-time greedy cut decision from the O(n log n) solution. */
        if (f->pos < 0) {
            int maximum = 0;
            for (int p = f->end; p-- > offset[x];) {
                int v = adjacency[p];
                if (v != f->parent) { maximum = v; break; }
            }
            if (!returned && in_cycle[f->parent] && in_cycle[x] &&
                in_cycle[maximum] && maximum > f->next_after) {
                returned = 1;
                f->cut_neighbor = maximum;
            }
            f->pos = offset[x];
        }

        int p = f->pos;
        while (p < f->end &&
               (adjacency[p] == f->parent ||
                adjacency[p] == f->cut_neighbor)) ++p;
        if (p == f->end) {
            --sp;
            continue;
        }

        int child = adjacency[p++];
        f->pos = p;
        if (visited[child]) continue;

        int look = p;
        while (look < f->end &&
               (adjacency[look] == f->parent ||
                adjacency[look] == f->cut_neighbor)) ++look;
        int next_after = look < f->end ? adjacency[look] : f->next_after;

        visited[child] = 1;
        *out++ = ' ';
        out = write_u32(out, (u32)child);
        ++sp;
        stack_[sp] = (Frame){child, x, next_after,
                             -1, offset[child + 1], 0};
    }

    *out++ = '\n';
    info->stdout_size = (duck_u64)(out - info->stdout_ptr);
}

#ifndef LOCAL
__attribute__((noreturn))
void __libc_start_main(void *unused, long argc, char **argv) {
    (void)unused;
    DuckInfo *info = duck_info(argc, argv);
    run(info);
    duck_exit();
}
int main(void) {}
#else
extern long read(int, void *, unsigned long);
extern long write(int, const void *, unsigned long);
static char local_in[16000000], local_out[8000000];
int main(void) {
    long n = read(0, local_in, sizeof(local_in));
    DuckInfo info = {0};
    info.stdin_ptr = local_in;
    info.stdin_size = (duck_u64)n;
    info.stdout_ptr = local_out;
    run(&info);
    write(1, local_out, info.stdout_size);
    return 0;
}
#endif

评测结果