QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#479727#999. 边双连通分量NOI_AK_ME#AC ✓26ms21584kbC++2318.1kb2024-07-15 20:34:132024-07-15 20:34:13

Judging History

你现在查看的是最新测评结果

  • [2024-07-15 20:34:13]
  • 评测
  • 测评结果:AC
  • 用时:26ms
  • 内存:21584kb
  • [2024-07-15 20:34:13]
  • 提交

answer

#include <algorithm>
#include <bit>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstring>
#include <numeric>
#include <vector>
#include <string>
#ifndef __OY_LINUXIO__
#define __OY_LINUXIO__
#ifdef __unix__
#include <sys/mman.h>
#include <sys/stat.h>
#endif
#if __cpp_constexpr >= 201907L
#define CONSTEXPR20 constexpr
#define INLINE20 constexpr
#else
#define CONSTEXPR20
#define INLINE20 inline
#endif
#define cin OY::LinuxIO::InputHelper<>::get_instance()
#define cout OY::LinuxIO::OutputHelper::get_instance()
#define endl '\n'
#ifndef INPUT_FILE
#define INPUT_FILE "in.txt"
#endif
#ifndef OUTPUT_FILE
#define OUTPUT_FILE "out.txt"
#endif
namespace OY {
    namespace LinuxIO {
        static constexpr size_t INPUT_BUFFER_SIZE = 1 << 26, OUTPUT_BUFFER_SIZE = 1 << 20;
#ifdef OY_LOCAL
        static constexpr char input_file[] = INPUT_FILE, output_file[] = OUTPUT_FILE;
#else
        static constexpr char input_file[] = "", output_file[] = "";
#endif
        template <typename U, size_t E>
        struct TenPow {
            static constexpr U value = TenPow<U, E - 1>::value * 10;
        };
        template <typename U>
        struct TenPow<U, 0> {
            static constexpr U value = 1;
        };
        struct InputPre {
            uint32_t m_data[0x10000];
            CONSTEXPR20 InputPre() {
                std::fill(m_data, m_data + 0x10000, -1);
                for (size_t i = 0, val = 0; i != 10; i++)
                    for (size_t j = 0; j != 10; j++) m_data[0x3030 + i + (j << 8)] = val++;
            }
        };
        struct OutputPre {
            uint32_t m_data[10000];
            CONSTEXPR20 OutputPre() {
                uint32_t *c = m_data;
                for (size_t i = 0; i != 10; i++)
                    for (size_t j = 0; j != 10; j++)
                        for (size_t k = 0; k != 10; k++)
                            for (size_t l = 0; l != 10; l++) *c++ = i + (j << 8) + (k << 16) + (l << 24) + 0x30303030;
            }
        };
        template <size_t MMAP_SIZE = 1 << 30>
        struct InputHelper {
            static INLINE20 InputPre pre{};
            struct stat m_stat;
            char *m_p, *m_c, *m_end;
            InputHelper(FILE *file = stdin) {
#ifdef __unix__
                auto fd = fileno(file);
                fstat(fd, &m_stat);
                m_c = m_p = (char *)mmap(nullptr, m_stat.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
                m_end = m_p + m_stat.st_size;
#else
                uint32_t size = fread(m_c = m_p = new char[INPUT_BUFFER_SIZE], 1, INPUT_BUFFER_SIZE, file);
                m_end = m_p + size;
#endif
            }
            static InputHelper<MMAP_SIZE> &get_instance() {
                static InputHelper<MMAP_SIZE> s_obj(*input_file ? fopen(input_file, "rt") : stdin);
                return s_obj;
            }
            template <typename Tp, typename std::enable_if<std::is_unsigned<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
            InputHelper &operator>>(Tp &x) {
                x = 0;
                while (!isdigit(*m_c)) m_c++;
                x = *m_c++ ^ '0';
                while (~pre.m_data[*reinterpret_cast<uint16_t *&>(m_c)]) x = x * 100 + pre.m_data[*reinterpret_cast<uint16_t *&>(m_c)++];
                if (isdigit(*m_c)) x = x * 10 + (*m_c++ ^ '0');
                return *this;
            }
            template <typename Tp, typename std::enable_if<std::is_signed<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
            InputHelper &operator>>(Tp &x) {
                typename std::make_unsigned<Tp>::type t{};
                bool sign{};
                while (!isdigit(*m_c)) sign = (*m_c++ == '-');
                t = *m_c++ ^ '0';
                while (~pre.m_data[*reinterpret_cast<uint16_t *&>(m_c)]) t = t * 100 + pre.m_data[*reinterpret_cast<uint16_t *&>(m_c)++];
                if (isdigit(*m_c)) t = t * 10 + (*m_c++ ^ '0');
                x = sign ? -t : t;
                return *this;
            }
            InputHelper &operator>>(char &x) {
                while (*m_c <= ' ') m_c++;
                x = *m_c++;
                return *this;
            }
            InputHelper &operator>>(std::string &x) {
                while (*m_c <= ' ') m_c++;
                char *c = m_c;
                while (*c > ' ') c++;
                x.assign(m_c, c - m_c), m_c = c;
                return *this;
            }
            InputHelper &operator>>(std::string_view &x) {
                while (*m_c <= ' ') m_c++;
                char *c = m_c;
                while (*c > ' ') c++;
                x = std::string_view(m_c, c - m_c), m_c = c;
                return *this;
            }
        };
        struct OutputHelper {
            static INLINE20 OutputPre pre{};
            FILE *m_file;
            char m_p[OUTPUT_BUFFER_SIZE], *m_c, *m_end;
            OutputHelper(FILE *file = stdout) {
                m_file = file;
                m_c = m_p, m_end = m_p + OUTPUT_BUFFER_SIZE;
            }
            ~OutputHelper() { flush(); }
            static OutputHelper &get_instance() {
                static OutputHelper s_obj(*output_file ? fopen(output_file, "wt") : stdout);
                return s_obj;
            }
            void flush() { fwrite(m_p, 1, m_c - m_p, m_file), m_c = m_p; }
            OutputHelper &operator<<(char x) {
                if (m_end - m_c < 20) flush();
                *m_c++ = x;
                return *this;
            }
            OutputHelper &operator<<(std::string_view s) {
                if (m_end - m_c < s.size()) flush();
                memcpy(m_c, s.data(), s.size()), m_c += s.size();
                return *this;
            }
            OutputHelper &operator<<(uint64_t x) {
                if (m_end - m_c < 20) flush();
#define CASEW(w)                                                           \
    case TenPow<uint64_t, w - 1>::value... TenPow<uint64_t, w>::value - 1: \
        *(uint32_t *)m_c = pre.m_data[x / TenPow<uint64_t, w - 4>::value]; \
        m_c += 4, x %= TenPow<uint64_t, w - 4>::value;
                switch (x) {
                    CASEW(19);
                    CASEW(15);
                    CASEW(11);
                    CASEW(7);
                    case 100 ... 999:
                        *(uint32_t *)m_c = pre.m_data[x * 10];
                        m_c += 3;
                        break;
                        CASEW(18);
                        CASEW(14);
                        CASEW(10);
                        CASEW(6);
                    case 10 ... 99:
                        *(uint32_t *)m_c = pre.m_data[x * 100];
                        m_c += 2;
                        break;
                        CASEW(17);
                        CASEW(13);
                        CASEW(9);
                        CASEW(5);
                    case 0 ... 9:
                        *m_c++ = '0' + x;
                        break;
                    default:
                        *(uint32_t *)m_c = pre.m_data[x / TenPow<uint64_t, 16>::value];
                        m_c += 4;
                        x %= TenPow<uint64_t, 16>::value;
                        CASEW(16);
                        CASEW(12);
                        CASEW(8);
                    case 1000 ... 9999:
                        *(uint32_t *)m_c = pre.m_data[x];
                        m_c += 4;
                        break;
                }
#undef CASEW
                return *this;
            }
            OutputHelper &operator<<(uint32_t x) {
                if (m_end - m_c < 20) flush();
#define CASEW(w)                                                           \
    case TenPow<uint32_t, w - 1>::value... TenPow<uint32_t, w>::value - 1: \
        *(uint32_t *)m_c = pre.m_data[x / TenPow<uint32_t, w - 4>::value]; \
        m_c += 4, x %= TenPow<uint32_t, w - 4>::value;
                switch (x) {
                    default:
                        *(uint32_t *)m_c = pre.m_data[x / TenPow<uint32_t, 6>::value];
                        m_c += 4;
                        x %= TenPow<uint32_t, 6>::value;
                        CASEW(6);
                    case 10 ... 99:
                        *(uint32_t *)m_c = pre.m_data[x * 100];
                        m_c += 2;
                        break;
                        CASEW(9);
                        CASEW(5);
                    case 0 ... 9:
                        *m_c++ = '0' + x;
                        break;
                        CASEW(8);
                    case 1000 ... 9999:
                        *(uint32_t *)m_c = pre.m_data[x];
                        m_c += 4;
                        break;
                        CASEW(7);
                    case 100 ... 999:
                        *(uint32_t *)m_c = pre.m_data[x * 10];
                        m_c += 3;
                        break;
                }
#undef CASEW
                return *this;
            }
            OutputHelper &operator<<(int64_t x) {
                if (x >= 0)
                    return (*this) << uint64_t(x);
                else
                    return (*this) << '-' << uint64_t(-x);
            }
            OutputHelper &operator<<(int32_t x) {
                if (x >= 0)
                    return (*this) << uint32_t(x);
                else
                    return (*this) << '-' << uint32_t(-x);
            }
        };
    }
}
#endif
#ifndef __OY_TARJAN_BRIDGE__
#define __OY_TARJAN_BRIDGE__
namespace OY {
    namespace EBCC {
        using size_type = uint32_t;
        template <bool GetBridge, bool GetEBCC, size_type MAX_VERTEX, size_type MAX_EDGE>
        struct Solver {
            struct info {
                size_type m_dfn, m_low;
            };
            static info s_info_buffer[MAX_VERTEX];
            static size_type s_ebcc_buffer[MAX_VERTEX * 3], s_use_count, s_edge_use_count;
            static bool s_buffer[MAX_EDGE];
            info *m_info;
            size_type m_vertex_cnt, m_edge_cnt, m_dfn_cnt, m_bridge_cnt, m_ebcc_cnt, m_stack_len, *m_starts, *m_stack, *m_ebccs;
            bool *m_is_bridge;
            template <typename Traverser>
            void _dfs(size_type i, size_type from, Traverser &&traverser) {
                size_type pos = m_stack_len;
                if constexpr (GetEBCC) m_stack[m_stack_len++] = i;
                m_info[i].m_dfn = m_info[i].m_low = m_dfn_cnt++;
                traverser(i, [&](size_type index, size_type to) {
                    if (!~m_info[to].m_dfn) {
                        _dfs(to, index, traverser);
                        m_info[i].m_low = std::min(m_info[i].m_low, m_info[to].m_low);
                    } else if (index != from)
                        m_info[i].m_low = std::min(m_info[i].m_low, m_info[to].m_dfn);
                });
                if (m_info[i].m_low != m_info[i].m_dfn) return;
                if constexpr (GetEBCC) std::copy(m_stack + pos, m_stack + m_stack_len, m_ebccs + (m_starts[m_ebcc_cnt++] = m_dfn_cnt - m_stack_len)), m_stack_len = pos;
                if constexpr (GetBridge)
                    if (~from) m_is_bridge[from] = true, m_bridge_cnt++;
            }
            Solver(size_type vertex_cnt, size_type edge_cnt) { m_vertex_cnt = vertex_cnt, m_edge_cnt = edge_cnt, m_dfn_cnt = m_bridge_cnt = m_ebcc_cnt = m_stack_len = 0, m_info = s_info_buffer + s_use_count, m_starts = s_ebcc_buffer + s_use_count * 3, m_stack = s_ebcc_buffer + s_use_count * 3 + m_vertex_cnt, m_ebccs = s_ebcc_buffer + s_use_count * 3 + m_vertex_cnt * 2, m_is_bridge = s_buffer + s_edge_use_count, s_use_count += m_vertex_cnt, s_edge_use_count += m_edge_cnt; }
            template <typename Traverser>
            void run(Traverser &&traverser) {
                for (size_type i = 0; i != m_vertex_cnt; i++) m_info[i].m_dfn = -1;
                for (size_type i = 0; i != m_vertex_cnt; i++)
                    if (!~m_info[i].m_dfn) _dfs(i, -1, traverser);
                if constexpr (GetEBCC) m_starts[m_ebcc_cnt] = m_vertex_cnt;
            }
            template <typename Callback>
            void do_for_each_ebcc(Callback &&call) {
                for (size_type i = 0, cur = m_starts[0], end = m_starts[1]; i != m_ebcc_cnt; cur = end, end = m_starts[++i + 1]) call(m_ebccs + cur, m_ebccs + end);
            }
            template <typename Callback>
            void do_for_each_bridge(Callback &&call) {
                for (size_type index = 0; index != m_edge_cnt; index++)
                    if (m_is_bridge[index]) call(index);
            }
        };
        template <bool GetBridge, bool GetEBCC, size_type MAX_VERTEX, size_type MAX_EDGE>
        typename Solver<GetBridge, GetEBCC, MAX_VERTEX, MAX_EDGE>::info Solver<GetBridge, GetEBCC, MAX_VERTEX, MAX_EDGE>::s_info_buffer[MAX_VERTEX];
        template <bool GetBridge, bool GetEBCC, size_type MAX_VERTEX, size_type MAX_EDGE>
        bool Solver<GetBridge, GetEBCC, MAX_VERTEX, MAX_EDGE>::s_buffer[MAX_EDGE];
        template <bool GetBridge, bool GetEBCC, size_type MAX_VERTEX, size_type MAX_EDGE>
        size_type Solver<GetBridge, GetEBCC, MAX_VERTEX, MAX_EDGE>::s_ebcc_buffer[MAX_VERTEX * 3];
        template <bool GetBridge, bool GetEBCC, size_type MAX_VERTEX, size_type MAX_EDGE>
        size_type Solver<GetBridge, GetEBCC, MAX_VERTEX, MAX_EDGE>::s_use_count;
        template <bool GetBridge, bool GetEBCC, size_type MAX_VERTEX, size_type MAX_EDGE>
        size_type Solver<GetBridge, GetEBCC, MAX_VERTEX, MAX_EDGE>::s_edge_use_count;
        template <size_type MAX_VERTEX, size_type MAX_EDGE>
        struct Graph {
            struct edge {
                size_type m_from, m_to;
            };
            struct adj {
                size_type m_index, m_to;
            };
            static size_type s_buffer[MAX_VERTEX << 1], s_use_count, s_edge_use_count;
            static edge s_edge_buffer[MAX_EDGE];
            static adj s_adj_buffer[MAX_EDGE << 1];
            size_type m_vertex_cnt, m_edge_cnt, *m_starts;
            edge *m_edges;
            adj *m_adj;
            mutable bool m_prepared;
            void _prepare() const {
                if (m_prepared) return;
                m_prepared = true;
                for (size_type i = 0; i != m_edge_cnt; i++) m_starts[m_edges[i].m_from + 1]++, m_starts[m_edges[i].m_to + 1]++;
                for (size_type i = 1; i != m_vertex_cnt + 1; i++) m_starts[i] += m_starts[i - 1];
                std::vector<size_type> cursor(m_starts, m_starts + m_vertex_cnt);
                for (size_type i = 0; i != m_edge_cnt; i++) {
                    size_type from = m_edges[i].m_from, to = m_edges[i].m_to;
                    m_adj[cursor[from]++] = {i, to}, m_adj[cursor[to]++] = {i, from};
                }
            }
            template <typename Callback>
            void operator()(size_type from, Callback &&call) const {
                for (size_type cur = m_starts[from], end = m_starts[from + 1]; cur != end; cur++) call(m_adj[cur].m_index, m_adj[cur].m_to);
            }
            Graph(size_type vertex_cnt = 0, size_type edge_cnt = 0) { resize(vertex_cnt, edge_cnt); }
            void resize(size_type vertex_cnt, size_type edge_cnt) {
                if (!(m_vertex_cnt = vertex_cnt)) return;
                m_prepared = false, m_starts = s_buffer + (s_use_count << 1), m_edges = s_edge_buffer + s_edge_use_count, m_adj = s_adj_buffer + (s_edge_use_count << 1), m_edge_cnt = 0, s_use_count += m_vertex_cnt, s_edge_use_count += edge_cnt;
            }
            void add_edge(size_type a, size_type b) { m_edges[m_edge_cnt++] = {a, b}; }
            template <bool GetBridge, bool GetEBCC>
            Solver<GetBridge, GetEBCC, MAX_VERTEX, MAX_EDGE> calc() const {
                _prepare();
                Solver<GetBridge, GetEBCC, MAX_VERTEX, MAX_EDGE> sol(m_vertex_cnt, m_edge_cnt);
                sol.run(*this);
                return sol;
            }
            std::vector<std::vector<size_type>> get_ebccs() const {
                _prepare();
                Solver<false, true, MAX_VERTEX, MAX_EDGE> sol(m_vertex_cnt, m_edge_cnt);
                sol.run(*this);
                std::vector<std::vector<size_type>> res;
                res.reserve(sol.m_ebcc_cnt);
                sol.do_for_each_ebcc([&](size_type *first, size_type *last) { res.emplace_back(first, last); });
                return res;
            }
            std::vector<size_type> get_bridges() const {
                _prepare();
                Solver<true, false, MAX_VERTEX, MAX_EDGE> sol(m_vertex_cnt, m_edge_cnt);
                sol.run(*this);
                std::vector<size_type> res;
                res.reserve(sol.m_bridge_cnt);
                sol.do_for_each_bridge([&](size_type index) { res.push_back(index); });
                return res;
            }
        };
        template <size_type MAX_VERTEX, size_type MAX_EDGE>
        size_type Graph<MAX_VERTEX, MAX_EDGE>::s_buffer[MAX_VERTEX << 1];
        template <size_type MAX_VERTEX, size_type MAX_EDGE>
        typename Graph<MAX_VERTEX, MAX_EDGE>::edge Graph<MAX_VERTEX, MAX_EDGE>::s_edge_buffer[MAX_EDGE];
        template <size_type MAX_VERTEX, size_type MAX_EDGE>
        typename Graph<MAX_VERTEX, MAX_EDGE>::adj Graph<MAX_VERTEX, MAX_EDGE>::s_adj_buffer[MAX_EDGE << 1];
        template <size_type MAX_VERTEX, size_type MAX_EDGE>
        size_type Graph<MAX_VERTEX, MAX_EDGE>::s_use_count;
        template <size_type MAX_VERTEX, size_type MAX_EDGE>
        size_type Graph<MAX_VERTEX, MAX_EDGE>::s_edge_use_count;
    }
}
#endif
static constexpr uint32_t N = 200000, M = 200000;
int main() {
    uint32_t n, m;
    cin >> n >> m;
    OY::EBCC::Graph<N, M> G(n, m);
    for (uint32_t i = 0; i != m; i++) {
        uint32_t a, b;
        cin >> a >> b;
        G.add_edge(a, b);
    }
    auto sol = G.calc<false, true>();
    cout << sol.m_ebcc_cnt << endl;
    sol.do_for_each_ebcc([&](auto first, auto last) {
        cout << last - first;
        for (auto it = first; it != last; ++it) cout << ' ' << *it;
        cout << endl;
    });
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 9920kb

input:

4 5
0 2
0 1
3 0
2 1
2 3

output:

1
4 0 2 1 3

result:

ok OK

Test #2:

score: 0
Accepted
time: 0ms
memory: 9824kb

input:

13 21
4 5
8 7
12 3
3 10
1 5
10 2
0 0
11 4
2 12
9 1
9 0
7 8
7 6
9 1
8 2
12 10
11 0
8 6
3 2
5 9
4 11

output:

3
6 0 9 1 5 4 11
3 8 7 6
4 2 10 3 12

result:

ok OK

Test #3:

score: 0
Accepted
time: 1ms
memory: 9756kb

input:

2 2
0 1
1 0

output:

1
2 0 1

result:

ok OK

Test #4:

score: 0
Accepted
time: 26ms
memory: 21584kb

input:

200000 200000
127668 148778
77100 11865
85144 199231
39485 84917
102044 187263
130204 174776
26220 198288
162188 12078
92196 146334
120537 38083
150353 160479
18707 6545
101149 25450
62271 9177
38892 6454
11709 191939
89247 145109
140599 121858
197410 148980
55975 169098
128576 59852
68224 182347
89...

output:

105340
1 130053
1 109379
1 16951
1 96939
1 134977
1 83121
1 114344
1 49994
1 179006
1 197312
1 73479
1 106040
1 50807
1 165221
1 166649
1 68272
1 38289
1 142682
1 99836
1 12028
1 102803
1 27099
1 114474
1 82079
1 104348
1 189374
1 92254
1 150379
1 159181
1 179811
1 140286
1 82857
1 100000
1 127708
1...

result:

ok OK

Test #5:

score: 0
Accepted
time: 26ms
memory: 21424kb

input:

200000 200000
150762 148756
172967 108322
69862 125085
84513 111056
141009 156725
36311 103205
31879 79919
62895 63377
21697 115522
161610 160423
113104 10277
106927 168428
136657 198931
52292 164110
149020 7038
115111 112823
35584 124385
45429 191603
96444 30523
195578 149089
160105 58103
139792 27...

output:

104955
1 125898
1 70394
1 53869
1 104669
1 129081
1 100681
1 41198
1 70879
1 112530
1 14934
1 108660
1 66365
1 24383
1 34481
1 138878
1 86552
1 89618
1 38043
1 54490
1 66419
1 120222
1 140638
1 17682
1 72554
1 89319
1 193209
1 93
1 171935
1 46988
1 199955
1 24166
1 9540
1 16383
1 642
1 137446
1 1176...

result:

ok OK

Test #6:

score: 0
Accepted
time: 15ms
memory: 21408kb

input:

200000 200000
53335 120202
193029 92221
8244 61648
50176 7825
97274 91479
85438 76999
26861 80116
162826 198446
160509 95916
143190 116619
121254 192931
121545 132273
149400 91882
97032 5048
179008 82221
187475 70697
159074 65868
158744 94466
120006 170635
36429 162768
61114 17876
131798 188508
1080...

output:

105649
1 29517
1 154139
1 130698
1 99640
1 140367
1 102247
1 198683
1 47273
1 187909
1 46326
1 22215
1 14473
1 189501
1 117986
1 18389
1 7084
1 132284
1 18675
1 32418
1 43432
1 156817
1 163858
1 151921
1 45282
1 153512
1 50415
1 7040
1 82344
1 100960
1 23893
1 81617
1 43176
1 143595
1 149608
1 60574...

result:

ok OK

Test #7:

score: 0
Accepted
time: 17ms
memory: 18784kb

input:

127669 148779
124640 77100
11865 117450
85144 68159
104241 39485
76372 84917
102044 56191
43704 26220
67216 31116
75749 123504
12078 92196
70006 15262
100591 74552
120537 38083
19281 29407
18707 6545
101149 25450
62271 9177
38892 6454
11709 119710
60867 89247
14037 9527
121858 66338
112298 81804
795...

output:

51131
1 94756
1 44517
1 47153
1 51915
1 12486
1 12214
1 98478
1 14748
1 53706
1 38686
1 22698
1 123435
1 15671
1 108457
1 98869
1 23082
1 76922
1 81699
1 29456
1 10660
1 83810
1 81407
1 30201
1 100714
1 103512
1 97281
1 24849
1 34179
1 80101
1 64953
1 113025
1 34833
1 30346
1 95686
1 84205
1 111115
...

result:

ok OK

Test #8:

score: 0
Accepted
time: 16ms
memory: 18988kb

input:

150763 148757
108322 69862
125085 84513
111056 141009
36311 103205
31879 79919
62895 63377
21697 115522
113104 10277
106927 136657
52292 149020
7038 115111
112823 35584
124385 45429
96444 30523
149089 58103
139792 27250
15883 109949
69372 132387
141930 113408
65522 128254
138198 141969
42522 92075
1...

output:

81019
1 6807
1 71992
1 6544
1 19114
1 55003
1 109404
1 63787
1 123739
1 41567
1 123431
1 59083
1 114167
1 61359
1 29409
1 59280
1 14684
1 112390
1 145242
1 66891
1 137369
1 84292
1 90202
1 100462
1 3126
1 127606
1 29538
1 76163
1 18555
1 140975
1 41127
1 127342
1 27999
1 93788
1 46914
1 11681
1 1340...

result:

ok OK

Test #9:

score: 0
Accepted
time: 5ms
memory: 15652kb

input:

53336 120203
26685 8244
50176 7825
31738 24370
25943 19902
11463 26861
29977 26309
14580 31754
1838 29437
30380 12118
51083 31633
1201 18328
26346 5295
48935 19027
31496 19906
41783 5048
47936 16685
5161 34107
15907 28002
332 27672
28930 39563
36429 31696
17876 726
42526 21682
35319 8727
17974 25252...

output:

3392
1 14547
1 33221
1 25373
1 49362
1 14444
1 28138
1 46202
1 10768
1 17577
1 12568
1 28744
1 37853
1 593
1 10608
1 5154
1 52185
1 33099
1 50252
1 8805
1 40238
1 20189
1 10803
1 26670
1 490
1 28244
1 13456
1 19261
1 31450
1 7461
1 20204
1 20001
1 18973
1 26131
1 6366
1 28795
1 43905
1 30583
1 26214...

result:

ok OK

Test #10:

score: 0
Accepted
time: 5ms
memory: 11572kb

input:

17707 71661
1354 3272
13699 17294
16733 9246
14993 5758
7252 2983
3813 6121
10450 14069
8088 11201
857 4420
12788 2032
11938 1465
10322 15171
14688 1857
2309 2742
2013 13200
14142 16319
10541 1922
10368 1516
7994 9092
3327 5166
13484 2876
15472 13522
15622 13479
3361 15314
15464 14974
17637 7535
435...

output:

75
1 17338
1 14797
1 3260
1 16007
1 9278
1 15699
1 12609
1 2548
1 12296
1 9486
1 7016
1 13118
1 8246
1 13212
1 5626
1 12473
1 14567
1 10678
1 8347
1 1786
1 8803
1 13636
1 5868
1 15222
1 5980
1 10131
1 12703
1 5504
1 13541
1 14057
1 9878
1 13333
1 17102
1 6026
1190 7795 7124 13409 7421 16327 14686 12...

result:

ok OK

Test #11:

score: 0
Accepted
time: 2ms
memory: 8356kb

input:

4294 17517
1175 3250
314 389
4272 3633
2938 1831
1307 2818
3321 347
1205 1428
2354 1478
1003 3898
1587 3443
1122 1512
2512 3995
348 3280
2064 1022
1834 2958
4281 1863
689 3613
2115 3708
1645 1488
1601 4181
916 4276
128 2626
4147 2868
87 1411
1802 1451
1254 2010
2936 3120
1065 277
1121 3284
3655 2849...

output:

29
1 3537
1 3593
1 3962
1 1431
1 3777
1 1575
198 2662 2474 3414 913 517 1232 2377 2561 1729 1396 3844 2169 2482 1754 1004 1474 2363 674 3884 839 188 2841 290 1191 691 2067 1558 1599 3478 3461 3430 478 3429 1492 3952 2278 1650 864 3422 3797 2929 2903 3016 919 1526 3361 4150 45 1498 176 3137 552 2071 ...

result:

ok OK

Test #12:

score: 0
Accepted
time: 0ms
memory: 13908kb

input:

26686 105813
14774 5315
22701 21346
1398 13888
18566 18745
22298 6181
21347 10653
16500 23768
2329 5818
17512 16769
25519 338
12580 3064
19467 21665
3978 13202
23556 25178
195 9695
1472 13111
22925 24074
3026 13281
17666 14469
22007 18680
4159 13152
20431 23814
6671 10788
24433 13211
9794 12608
3264...

output:

137
1 23394
1 12475
1 2118
1 13345
1 2141
1 22100
1 2499
1 24377
1 1538
1 8709
1 6744
1 16355
1 10300
1 1219
1 10070
1 18834
1 5841
1 13843
1 23868
1 15273
1 26505
1 6022
1 20785
1 8727
1 18510
1 651
1 15559
1 8682
1 17160
1 8793
1 22179
1 26437
1 5458
1 12486
1 371
1 10917
1 24928
1 22401
1 25296
1...

result:

ok OK

Test #13:

score: 0
Accepted
time: 8ms
memory: 12412kb

input:

36033 148595
33366 22486
14414 23855
2694 30361
16352 31902
27993 2048
4707 31743
30610 12884
23278 27069
10529 20914
2030 30015
24554 15673
10184 29423
17825 20383
34077 1181
25518 26129
6355 8810
2857 21736
25108 34280
14992 24299
32649 20227
34529 10407
23194 29913
10451 319
34666 8904
30811 3003...

output:

150
1 7683
1 26444
1 2952
1 909
1 29816
1 28914
1 24825
1 7652
1 32601
1 15933
1 35383
1 10070
1 206
1 26526
1 2237
1 28026
1 2228
1 10445
1 20693
1 31025
1 16543
1 14407
7961 0 28838 10061 799 14110 29442 20494 31404 26764 28991 24773 12616 16339 23468 22326 17303 32977 23324 10223 29873 3162 9601 ...

result:

ok OK

Test #14:

score: 0
Accepted
time: 0ms
memory: 11240kb

input:

14868 57739
5724 2103
9214 3074
2269 531
3811 13162
5199 12632
6337 12078
12592 4977
3553 6975
5063 6622
1221 13056
4252 3705
7547 7879
1702 3685
4058 2503
7540 9423
4280 12228
574 6265
11876 2711
4805 7605
1468 4802
6921 1954
6350 2733
4429 5862
13549 14543
13809 5357
1509 11478
87 2676
6299 7060
1...

output:

80
1 13153
1 12664
1 2754
1 4425
1 14692
1 4662
1 8044
1 12898
1 14131
1 7206
1 9966
1 4604
1 10801
1 14211
1 9132
1 5731
1 2864
1 10995
1 11626
1 8758
1 13598
1 14166
1 5009
1 5562
1 14061
1 4108
1 10861
1 2470
1 646
1 2033
1 11655
1 9659
1 14058
1 2698
1 150
1 1860
1 13959
1 9764
1 10345
1 84
1 51...

result:

ok OK

Test #15:

score: 0
Accepted
time: 1ms
memory: 7884kb

input:

53 43
32 44
25 10
24 49
20 28
28 44
16 12
37 48
46 36
30 47
25 3
17 31
19 17
29 42
25 44
30 3
31 21
2 34
42 12
22 50
12 52
39 10
0 46
29 1
12 21
3 0
11 31
42 25
4 51
26 36
19 48
39 26
5 21
7 41
29 34
38 47
29 8
26 17
42 46
36 20
39 30
13 27
28 31
27 24

output:

37
1 38
1 47
1 32
1 37
1 48
1 19
1 16
1 1
1 2
1 34
1 8
1 29
1 52
1 5
1 11
17 0 46 36 26 39 10 25 3 30 44 28 20 31 17 21 12 42
1 51
1 4
1 6
1 41
1 7
1 9
1 49
1 24
1 27
1 13
1 14
1 15
1 18
1 50
1 22
1 23
1 33
1 35
1 40
1 43
1 45

result:

ok OK

Test #16:

score: 0
Accepted
time: 1ms
memory: 9948kb

input:

70 21
39 34
29 33
38 53
37 7
47 64
47 17
65 66
60 39
37 47
19 68
14 28
39 41
52 55
0 60
59 16
11 40
11 33
35 26
0 11
24 17
26 43

output:

70
1 34
1 41
1 39
1 60
1 40
1 29
1 33
1 11
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 64
1 24
1 17
1 47
1 37
1 7
1 8
1 9
1 10
1 12
1 13
1 28
1 14
1 15
1 59
1 16
1 18
1 68
1 19
1 20
1 21
1 22
1 23
1 25
1 35
1 43
1 26
1 27
1 30
1 31
1 32
1 36
1 53
1 38
1 42
1 44
1 45
1 46
1 48
1 49
1 50
1 51
1 55
1 52
1 54
1 56
1 ...

result:

ok OK

Test #17:

score: 0
Accepted
time: 1ms
memory: 10024kb

input:

88 139
5 61
52 80
0 17
50 87
62 71
25 69
10 46
44 86
11 38
17 35
73 49
24 47
39 83
8 66
55 56
64 45
83 41
59 35
76 24
2 70
11 77
80 58
84 86
30 50
23 54
36 74
12 10
62 75
33 34
43 28
77 29
10 46
77 33
26 48
32 38
52 79
15 30
25 57
86 0
46 75
81 60
35 83
66 87
25 86
19 85
9 38
15 64
59 82
0 53
40 66
...

output:

16
1 82
1 45
1 47
1 54
1 68
1 34
1 13
1 74
1 42
1 18
1 12
1 31
1 53
73 0 17 35 59 10 46 75 62 71 56 55 1 9 38 11 77 29 87 50 30 15 64 4 24 76 23 21 2 70 80 52 79 48 26 39 83 41 22 63 19 85 14 6 49 73 33 40 66 8 86 44 58 84 67 25 69 36 27 57 61 5 37 28 43 81 60 20 72 78 3 65 7 32
1 16
1 51

result:

ok OK

Test #18:

score: 0
Accepted
time: 1ms
memory: 9892kb

input:

53 185
48 40
23 7
45 7
6 42
13 6
45 1
18 28
47 14
11 15
27 9
50 44
23 47
20 27
18 19
2 19
18 49
32 49
9 12
11 0
32 49
22 14
8 48
41 28
30 43
4 21
7 22
28 30
17 11
19 30
44 7
46 8
50 45
35 48
29 47
4 26
16 39
37 25
38 12
19 52
28 41
23 31
33 34
6 15
44 24
0 6
26 22
49 43
4 31
20 38
43 39
41 39
51 40
...

output:

3
16 21 4 26 22 14 47 23 7 45 1 24 44 50 5 29 31
20 0 11 15 6 42 20 27 9 12 38 8 48 40 51 46 10 13 35 17 3
17 2 19 18 28 41 39 16 49 32 43 30 33 34 36 25 37 52

result:

ok OK

Test #19:

score: 0
Accepted
time: 1ms
memory: 7756kb

input:

70 252
63 36
64 48
26 34
43 37
30 53
67 64
26 19
25 54
28 44
52 60
4 22
43 48
14 48
12 50
37 23
28 40
48 54
60 23
43 46
7 5
29 39
5 13
57 60
1 23
33 8
59 39
3 29
5 8
34 11
44 40
39 19
40 17
42 48
39 19
49 46
0 48
46 45
57 67
43 60
56 59
32 42
6 54
56 69
23 43
38 65
66 24
0 64
16 10
23 1
4 16
37 49
5...

output:

1
70 0 48 64 67 57 60 52 32 42 51 15 25 54 6 5 7 62 59 39 29 3 34 26 19 68 13 21 9 55 17 40 28 44 66 24 47 16 10 36 63 22 4 65 38 31 27 58 20 11 56 69 61 8 33 35 41 18 30 53 12 50 2 49 46 43 37 23 1 14 45

result:

ok OK

Test #20:

score: 0
Accepted
time: 1ms
memory: 7856kb

input:

88 390
74 40
14 37
44 66
7 49
12 4
39 48
56 76
46 40
80 30
5 39
52 0
40 79
0 11
34 41
43 80
54 62
61 41
54 37
31 81
59 66
23 59
47 84
16 85
68 29
31 63
4 55
27 5
26 68
14 84
16 34
82 16
62 54
46 15
65 63
58 83
5 36
67 19
65 42
35 25
82 73
55 59
28 36
22 38
46 79
61 34
51 40
69 42
36 5
26 38
86 14
22...

output:

3
6 36 5 39 48 60 27
6 20 76 56 9 77 33
76 0 52 75 45 79 40 74 51 15 46 18 70 21 58 83 3 19 67 31 81 65 63 13 8 69 42 10 84 47 78 62 54 37 14 86 7 49 24 50 6 64 28 11 32 25 35 87 82 16 85 41 34 61 57 73 80 30 43 72 1 2 66 44 53 55 4 12 22 38 26 68 29 23 59 71 17

result:

ok OK