QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#54956#2475. Bank RobberysebinkimAC ✓48ms3904kbC++22.3kb2022-10-11 18:56:062022-10-11 18:56:08

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-11 18:56:08]
  • 评测
  • 测评结果:AC
  • 用时:48ms
  • 内存:3904kb
  • [2022-10-11 18:56:06]
  • 提交

answer

#include <bits/stdc++.h>
// #define JUDGE

#include <sys/stat.h>
#include <cassert>
#include <unistd.h>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>

using namespace std;
typedef long long int ll;
typedef vector<vector<ll>> graph;
// push_back insert lower_bound upper_bound erase

#ifdef JUDGE
#define RESULT_OK 42
#define RESULT_WA 43
#define RESULT_JE 2
#else
#define RESULT_OK 0
#define RESULT_WA 1
#define RESULT_JE 2
#endif

#define DECISION_ATTACK "ATTACK"
#define DECISION_DEFEND "DEFEND"

#define MAX_TURNS 365

#define INF (1ll<<60)

string ROLE="U";


/* Utility functions for writing output validators for the Kattis
 * problem format.
 *
 * The primary functions and variables available are the following.
 * In many cases, the only functions needed are "init_io",
 * "wrong_answer", and "accept".
 *
 * - init_io(argc, argv):
 *        initialization
 *
 * - judge_in, judge_ans, author_out:
 *        std::istream objects for judge input file, judge answer
 *        file, and submission output file.
 *
 * - accept():
 *        exit and give Accepted!
 *
 * - accept_with_score(double score):
 *        exit with Accepted and give a score (for scoring problems)
 *
 * - judge_message(std::string msg, ...):
 *        printf-style function for emitting a judge message (a
 *        message that gets displayed to a privileged user with access
 *        to secret data etc).
 *
 * - wrong_answer(std::string msg, ...):
 *        printf-style function for exitting and giving Wrong Answer,
 *        and emitting a judge message (which would typically explain
 *        the cause of the Wrong Answer)
 *
 * - judge_error(std::string msg, ...):
 *        printf-style function for exitting and giving Judge Error,
 *        and emitting a judge message (which would typically explain
 *        the cause of the Judge Error)
 *
 * - author_message(std::string msg, ...):
 *        printf-style function for emitting an author message (a
 *        message that gets displayed to the author of the
 *        submission).  (Use with caution, and be careful not to let
 *        it leak information!)
 *
 */

typedef void (*feedback_function)(const std::string &, ...);

const std::string FILENAME_AUTHOR_MESSAGE = "teammessage.txt";
const std::string FILENAME_JUDGE_MESSAGE = "judgemessage.txt";
const std::string FILENAME_JUDGE_ERROR = "judgeerror.txt";
const std::string FILENAME_SCORE = "score.txt";

#define USAGE "%s: judge_in judge_ans feedback_dir < author_out\n"

#ifdef JUDGE
std::ifstream judge_in, judge_ans;
#endif

std::istream author_out(std::cin.rdbuf());

char *feedbackdir = NULL;

void vreport_feedback(const std::string &category,
                      const std::string &msg,
                      va_list pvar) {
    std::ostringstream fname;
    if (feedbackdir)
        fname << feedbackdir << '/';
    fname << category;
#ifdef JUDGE
    FILE *f = fopen(fname.str().c_str(), "a");
    assert(f);
    vfprintf(f, msg.c_str(), pvar);
    fclose(f);
#else
    vfprintf(stderr, msg.c_str(), pvar);
#endif
}

void report_feedback(const std::string &category, const std::string &msg, ...) {
    va_list pvar;
    va_start(pvar, msg);
    vreport_feedback(category, msg, pvar);
}

void author_message(const std::string &msg, ...) {
    va_list pvar;
    va_start(pvar, msg);
    vreport_feedback(FILENAME_AUTHOR_MESSAGE, msg, pvar);
}

void judge_message(const std::string &msg, ...) {
    va_list pvar;
    va_start(pvar, msg);
    vreport_feedback(FILENAME_JUDGE_MESSAGE, msg, pvar);
}

void wrong_answer(const std::string &msg, ...) {
#ifdef JUDGE
    va_list pvar;
    va_start(pvar, msg);
    vreport_feedback(FILENAME_JUDGE_MESSAGE, msg, pvar);
#endif
#ifdef JUDGE
    usleep(150000); // needed?
#endif
    exit(RESULT_WA);
}

void judge_error(const std::string &msg, ...) {
#ifdef JUDGE
    va_list pvar;
    va_start(pvar, msg);
    vreport_feedback(FILENAME_JUDGE_ERROR, msg, pvar);
#endif
    assert(0);
}

void accept() {
#ifdef JUDGE
    usleep(150000); // needed?
#endif
    exit(RESULT_OK);
}

void accept_with_score(double scorevalue) {
    report_feedback(FILENAME_SCORE, "%.9le", scorevalue);
    exit(RESULT_OK);
}


bool is_directory(const char *path) {
    struct stat entry;
    return stat(path, &entry) == 0 && S_ISDIR(entry.st_mode);
}

void init_io(int argc, char **argv) {
#ifdef JUDGE
    if(argc < 4) {
        fprintf(stderr, USAGE, argv[0]);
        judge_error("Usage: %s judgein judgeans feedbackdir [opts] < userout", argv[0]);
    }

    // Set up feedbackdir first, as that allows us to produce feedback
    // files for errors in the other parameters.
    if (!is_directory(argv[3])) {
        judge_error("%s: %s is not a directory\n", argv[0], argv[3]);
    }
    feedbackdir = argv[3];

    judge_in.open(argv[1], std::ios_base::in);
    if (judge_in.fail()) {
        judge_error("%s: failed to open %s\n", argv[0], argv[1]);
    }

    judge_ans.open(argv[2], std::ios_base::in);
    if (judge_ans.fail()) {
        judge_error("%s: failed to open %s\n", argv[0], argv[2]);
    }

    author_out.rdbuf(std::cin.rdbuf());
#endif
}
///////////////////////////////////////////////////////////////////////////////
void wrong_eof(const char* msg) {
    // if the program crashed, give the runner better chance to notice before we issue WA
    usleep(150000);
    wrong_answer(msg);
}
///////////////////////////////////////////////////////////////////////////////


struct Val{
    ll inner;
    ll guards;
    bool has_occupied_leaf;
    ll unoccupied_leaf_id;
    friend ostream & operator<<(ostream &os, const Val &v){
        os << v.inner << ' ' << v.guards << ' ' << v.has_occupied_leaf << ' ' << v.unoccupied_leaf_id;
        return os;
    }
};

// optimal defending strategy
struct Tree{
    ll N;
    ll root;
    set<ll> leaves, inner;
    set<pair<ll,ll>> edges;
    vector<ll> parent;
    vector<vector<ll>> children;
    vector<ll> depth;
    multiset<ll> configuration;
    ll last_attack;
    graph g;
    vector<pair<ll,ll>> edge_order;

    Tree(graph g,set<pair<ll,ll>> edges):N(g.size()),root(0),edges(edges),parent(N),children(N),depth(N,-1),g(g){
        judge_message("initializing structure\n");
        for(ll i=0; i<N; ++i) if(g[i].size() >= 2) inner.insert(i); else leaves.insert(i);
        root = *inner.begin();
        { // find centroid to have a nice root (mainly for defending)
            queue<ll> q;
            vector<ll> distance(N,-1);
            for(ll n : leaves){
                distance[n] = 0;
                q.push(n);
            }
            while(!q.empty()){
                ll el = q.front(); q.pop();
                for(ll n:g[el])if(distance[n] == -1){
                    distance[n] = distance[el]+1;
                    q.push(n);
                }
            }
            ll mx = -1, mxi=-1;
            for(ll i=0; i<N; ++i){
                if(distance[i] > mx){
                    mx = distance[i];
                    mxi = i;
                }
            }
            assert(mxi!=-1);
            root = mxi;
            judge_message("setting root to %lld\n",root);
        }
        if(leaves.begin() != leaves.end()){
            last_attack = *leaves.begin();
        }else{
            last_attack = *inner.begin();
        }
        { // initialize children, parents, & depth of the structure
            vector<bool> todo(N, true);
            queue<ll> q;
            q.push(root);
            depth[root] = 0;
            todo[root] = false;
            judge_message("structure search\n");
            while(!q.empty()){
                ll el = q.front(); q.pop();
                for(ll n:g[el])if(todo[n]){
                    q.push(n);
                    todo[n] = false;
                    parent[n] = el;
                    children[el].push_back(n);
                    depth[n] = depth[el] + 1;
                }
            }
        }
        judge_message("structure dfs\n");
        dfs(root,root);
        ll S = edge_order.size();
        for(ll i=0; i<S; ++i){
            auto p = edge_order[S-1-i];
            edge_order.push_back({p.second,p.first});
        }
        judge_message("structure end\n");
    }
    void dfs(ll el, ll from){
        for(ll n:g[el])if(n!=from){
            dfs(n, el);
            edge_order.push_back({n, el});
        }
    }
    void init(ll N){
        auto a = inner.begin();
        while((ll)configuration.size() < N && a!=inner.end()){
            configuration.insert(*a); ++a;
        }
        if((ll)configuration.size() == N){
            vector<ll> inner_v(inner.begin(),inner.end());
            // last_attack = inner_v[rand()%inner_v.size()];
            last_attack = root;
        }
        auto b = leaves.begin();
        while((ll)configuration.size() < N && b!=leaves.end()){
            configuration.insert(*b); ++b;
        }
    }
    void init(multiset<ll> defenders){
        configuration = defenders;
    }
    vector<pair<ll,ll>> defend(ll attack){
        if(!(0 <= attack && attack < N)){
           judge_message("attack %d out of bounds\n", attack);
            exit(RESULT_JE);
        }
        if(configuration.count(attack)){
            judge_message("no movement necessary\n");
            return vector<pair<ll,ll>>(); // no movement necessary
        }
        // find path from the last attack to the new attack
        vector<ll> prev(N, -1);
        queue<ll> q;
        q.push(attack);
        prev[attack] = -2;
        while(!q.empty()){
            ll el = q.front(); q.pop();
            for(ll n : g[el])if(prev[n]==-1){
                q.push(n);
                prev[n] = el;
            }
        }
        ll last = last_attack;
        vector<ll> path;
        while(last != -2){
            path.push_back(last);
            last = prev[last];
        }
        judge_message("found path from %lld to %lld with %lld vertices, moving guards along it\n", last_attack, attack, path.size());
        last_attack = attack;
        // move guards along the path so that the new vertex is covered
        bool encountered_empty_vertex = false;
        vector<pair<ll,ll>> res;
        for(ll i=0; i+1<(ll)path.size(); ++i){
            if(configuration.count(path[i])){ // may move only when a guard is present
                if(encountered_empty_vertex){
                    if(depth[path[i]] < depth[path[i+1]]){ // resetting the origin to be near the root if possible
                        res.push_back({path[i],path[i+1]});
                    }
                }else{
                    res.push_back({path[i],path[i+1]});
                }
            }else{
                encountered_empty_vertex = true; // empty vertex means that the strategy cannot be optimal, then we should not move vertices as long as they would move towards the root
            }
        }
        return res;
    }

    void move(const vector<pair<ll,ll>> &moves){
        // perform the moves
        judge_message("defender moved %lld  ", moves.size());
        for(auto &p:moves) {
            judge_message(" %lld->%lld", p.first, p.second);
        }
        judge_message("\n");
        for(auto p:moves) { // each moved guard exists
            auto it = configuration.find(p.first);
            if(it == configuration.end()){
                wrong_answer("defender is trying to move a non-existant guard %lld\n", p.first);
            }
        }
        for(auto p:moves) { // the guard is moved no more than once
            auto it = configuration.find(p.first);
            if(it == configuration.end()){
                wrong_answer("defender is trying to move a guard %lld more than once\n", p.first);
            }
            configuration.erase(it);
        }
        for(auto p:moves) {
            configuration.insert(p.second);
        }
        for(auto &p:moves) { // all moves are along edges
            if(!edges.count(p)){
                wrong_answer("defender moved from %lld to %lld where no edge is present\n", p.first, p.second);
            }
        }
        for(auto &p:configuration) { // end configuration has no doubled guards
            if(configuration.count(p) > 1){
                wrong_answer("defender moved multiple guards onto a single configuration %lld\n", p);
            }
        }
    }

    ll detect_attack_position(){
        map<pair<ll,ll>,Val> subtree;
        for(auto p : edge_order){
            ll from = p.first;
            ll to = p.second;
            bool is_leaf = leaves.count(from);
            ll occupied_by_guard = (ll)configuration.count(from);
            bool is_occupied_leaf = is_leaf && occupied_by_guard != 0;
            ll unoccupied_leaf_id = is_leaf && !is_occupied_leaf ? from : -1;
            Val v = {(ll)inner.count(from), occupied_by_guard, is_occupied_leaf, unoccupied_leaf_id};
            for(ll n : g[from])if(n!=to){
                auto prev_edge = make_pair(n,from);
                v.inner += subtree[prev_edge].inner;
                v.guards += subtree[prev_edge].guards;
                v.has_occupied_leaf |= subtree[prev_edge].has_occupied_leaf;
                v.unoccupied_leaf_id = max(v.unoccupied_leaf_id, subtree[prev_edge].unoccupied_leaf_id);
            }
            if(v.has_occupied_leaf) v.unoccupied_leaf_id = -1;
            subtree[p] = v;
        }
        ll best = -1;
        ll best_attack = INF;
        ll weak_point = INF;
        for(ll i=0; i<N; ++i){
            if(configuration.count(i) == 0 && leaves.count(i) == 0){
                for(ll n : g[i]){
                    auto vals = subtree[make_pair(i, n)];
                    if(vals.guards <= vals.inner){
                        if(depth[i] > best){
                            best = depth[i];
                            ll to_attack = -1;
                            for(ll nn : g[i])if(nn!=n){
                                Val &nn_vals = subtree[make_pair(nn, i)];
                                to_attack = max(to_attack, nn_vals.unoccupied_leaf_id);
                            }
                            best_attack = to_attack;
                            weak_point = i;
                        }
                    }
                }
            }
        }
        if(best == -1){
            // choose random non-occupied vertex
            set<ll> empty_positions;
            for(ll i=0; i<N; ++i) empty_positions.insert(i);
            for(ll n : configuration) empty_positions.erase(n);
            vector<ll> empty_arr(empty_positions.begin(),empty_positions.end());
            ll attack;
            if(empty_arr.size()){
                attack = empty_arr[rand()%empty_arr.size()];
            }else{
                vector<ll> confs(configuration.begin(),configuration.end());
                attack = confs[rand()%confs.size()];
            }
            judge_message("tough, no winning move; attacking randomly vertex %lld\n", attack);
            return attack;
        }else{
            judge_message(">>>>>>>>>>>>>>> a weak point found at %lld, attacking optimally\n", weak_point);
            return best_attack;
        }
    }
    ll optimum(){ return inner.size() + 1; }
};

int main(int argc, char **argv){
    init_io(argc, argv);
    judge_message("program running\n");
    srand(time(NULL));
    ll N, guards;
#ifdef JUDGE
    judge_in >> N >> guards;
    cout << N << ' ' << guards << endl;
#else
    cin >> N >> guards;
#endif

    // load tree
    graph g(N);
    assert(N<=100);
    set<pair<ll,ll>> edges;
    for(ll i=0; i<N-1; ++i){
        ll A, B;
#ifdef JUDGE
        judge_in >> A >> B;
        cout << A << ' ' << B << endl;
#else
        cin >> A >> B;
#endif
        g[A].push_back(B);
        g[B].push_back(A);
        edges.insert({A,B});
        edges.insert({B,A});
    }
    judge_message("loaded input graph:\n");
    judge_message("%lld %lld\n", N, guards);
    for(auto &p : edges) if(p.first <= p.second) judge_message("%lld %lld\n", p.first, p.second);

    // resolve optimal strategy
    Tree tree(g,edges);

    bool this_program_attacks;

#ifdef JUDGE
    judge_message("judge waiting for decision\n");
    string decision;
    cin >> decision;
    if(!cin.good()){
        wrong_answer("EOF obtained when loading contestant's decision\n");
    }
    if(decision != DECISION_ATTACK && decision != DECISION_DEFEND){
        wrong_answer("contestant's decision is malformed, got:%s instead of %s or %s\n", decision.c_str(), DECISION_ATTACK, DECISION_DEFEND);
    }
    judge_message("judge obtained decision, contestant decided to play %lld\n", decision);
    bool contestant_attacks = (decision == DECISION_ATTACK);
    this_program_attacks = !contestant_attacks;
#else
    ll optimal = tree.optimum();
    // decide what role to perform based on the number of provided guards
    bool should_attack = (guards < optimal);
    judge_message("C: printing decision\n");
    cout << (should_attack ? DECISION_ATTACK : DECISION_DEFEND) << endl;
    this_program_attacks = should_attack;
#endif
    ROLE = this_program_attacks ? "A" : "D";

    if(this_program_attacks){
        // ATTACK //////////////////////////////////////////////////////////////////////
        judge_message("loading defended vertices\n");
        multiset<ll> position;
        for(ll i=0; i<guards; ++i){ ll A; cin >> A; position.insert(A); }
        if(!cin.good()){
            wrong_answer("EOF obtained when loading defended vertices\n");
        }
        for(ll A : position) if(A < 0 || N <= A) wrong_answer("guard %lld is out of range [0,%lld)\n", A, N);
        set<ll> unique_guards;
        for(ll A : position) {
            if(unique_guards.count(A)) wrong_answer("initial position of guards has more than one guard on vertex %lld\n", A);
            unique_guards.insert(A);
        }
        judge_message("loaded defended vertices");
        for(ll n : position) judge_message(" %lld", n);
        judge_message("\n");
        tree.init(position);
        ll turn;
        for(turn=0; turn<MAX_TURNS-1; ++turn){
            // find a good place to attack
            ll attacked_vertex = tree.detect_attack_position();
            judge_message("attacking %lld\n", attacked_vertex);
            // perform the attack
            cout << attacked_vertex << endl;
            // load opponent's moves
            ll M;
            cin >> M;
            if(!cin.good()){
                judge_message("EOF obtained when loading moves; defender is giving up\n");
                judge_message("yay! I win; this was expected\n");
                accept();
            }
            vector<pair<ll,ll>> moves(M);
            for(auto &p:moves) cin >> p.first >> p.second;
            if(!cin.good()){
                wrong_answer("EOF obtained when loading moves\n");
            }
            // perform the moves
            tree.move(moves);
            // check that the moves defended the attacked position
            if(!tree.configuration.count(attacked_vertex)){
                judge_message("the attacked vertex %lld was not defended by the defender moves\n", attacked_vertex);
                judge_message("current defender configuration is");
                for(ll pos : tree.configuration) judge_message(" %lld", pos);
                judge_message("\n");
#ifdef JUDGE
                wrong_answer("the contestant was beaten in %lld turns; giving WA\n", turn);
#else
                judge_message("yay! I win; this was expected\n");
                accept();
#endif
                break;
            }
        }
#ifdef JUDGE
        judge_message("uff, I did not manage to beat the beaten in %lld turns; seems contestant defending strategy is good\n", turn);
        cout << -1 << endl;
#else
        judge_error("ERROR: the referential attacking solution was beaten, which should be impossible when it is in the role of the contestant solution\n");
#endif
        judge_message("ENDING\n");
    }else{
        // DEFENSE /////////////////////////////////////////////////////////////////////
        tree.init(guards);
        judge_message("printing defended vertices ");
        bool space = false;
        for(ll n:tree.configuration){ // print the initial configuration
            if(space)cout << ' ';
            space = true;
            cout << n;
            judge_message("%lld ", n);
        }
        judge_message("\n");
        cout << endl;
        judge_message("defending\n");
        ll turn=0, attack;
        judge_message("waiting for an attack\n");
        while(cin >> attack && attack != -1){
            judge_message("defending attack on %lld\n", attack);
            if(turn >= MAX_TURNS){
                wrong_answer("contestant did not mannage to beat the defender in %lld moves, he failed; give WA\n", turn);
            }
            turn += 1;
            if(attack < 0 || tree.N <= attack){
                wrong_answer("contestant attacked vertex out of bounds: %lld which should have been in [0,%lld)\n", attack, tree.N);
            }
            auto moves = tree.defend(attack);
            tree.move(moves);
            if(!tree.configuration.count(attack)){
                judge_message("I was not able to defend an attack on %lld\n", attack);
                judge_message("current defender configuration is:");
                for(ll pos : tree.configuration) judge_message(" %lld", pos);
                judge_message("\n");
#ifdef JUDGE
                judge_message("uff, I was beaten in %lld turns; contestant's solution seems to attack optimally\n", turn);
                accept();
#else
                judge_error("ERROR: the referential defensive solution was beaten, which should be impossible when it is in the role of the contestant solution\n");
#endif
            }
            cout << moves.size();
            for(auto p:moves) cout << " " << p.first << " " << p.second;
            cout << endl;
            judge_message("waiting for an attack\n");
        }
#ifdef JUDGE
        wrong_answer("the contestant was not able to beat me in %lld turns; giving WA\n", turn);
#else
        judge_message("yay! I win; this was expected\n");
#endif
        judge_message("ENDING\n");
    }

    accept();
}

详细

Test #1:

score: 100
Accepted
time: 22ms
memory: 3740kb

input:

6 3
0 1
0 2
0 3
3 4
3 5
4
2
5
1
2
5
1
5
1
2
1
2
1
5
4
2
5
1
2
5
4
5
2
1
4
5
2
5
1
2
4
2
4
5
1
2
5
4
5
4
1
5
1
2
5
2
5
1
2
4
5
4
2
1
5
1
2
1
4
5
4
2
5
4
1
2
4
2
4
1
2
5
1
2
4
2
1
5
4
5
2
1
2
4
1
4
5
4
5
2
4
5
4
2
5
2
1
5
4
5
2
4
5
1
5
2
5
2
5
1
4
2
1
4
1
5
4
5
2
4
5
1
5
2
1
2
1
4
1
4
2
1
5
1
4
1
2
5
...

output:

DEFEND
0 1 3
3 1 0 0 3 3 4
3 4 3 3 0 0 2
3 2 0 0 3 3 5
3 5 3 3 0 0 1
2 1 0 0 2
3 2 0 0 3 3 5
3 5 3 3 0 0 1
3 1 0 0 3 3 5
3 5 3 3 0 0 1
2 1 0 0 2
2 2 0 0 1
2 1 0 0 2
2 2 0 0 1
3 1 0 0 3 3 5
2 5 3 3 4
3 4 3 3 0 0 2
3 2 0 0 3 3 5
3 5 3 3 0 0 1
2 1 0 0 2
3 2 0 0 3 3 5
2 5 3 3 4
2 4 3 3 5
3 5 3 3 0 0 2
2...

result:

ok 

Test #2:

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

input:

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

output:

ATTACK
2
5
4

result:

ok 

Test #3:

score: 0
Accepted
time: 19ms
memory: 3880kb

input:

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

output:

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

result:

ok 

Test #4:

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

input:

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

output:

ATTACK
87
77
69
65
63
62

result:

ok 

Test #5:

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

input:

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

output:

ATTACK
21
17
15
14

result:

ok 

Test #6:

score: 0
Accepted
time: 3ms
memory: 3748kb

input:

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

output:

ATTACK
6
13
12

result:

ok 

Test #7:

score: 0
Accepted
time: 4ms
memory: 3788kb

input:

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

output:

ATTACK
2
4

result:

ok 

Test #8:

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

input:

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

output:

DEFEND
0 1 2 3 5 7 8
5 3 0 0 1 1 7 7 8 8 12
7 12 8 8 7 7 1 1 0 0 2 2 5 5 10
7 10 5 5 2 2 0 0 1 1 7 7 8 8 13
4 13 8 8 7 7 1 1 6
4 6 1 1 7 7 8 8 12
2 12 8 8 13
4 13 8 8 7 7 1 1 6
5 6 1 1 0 0 2 2 5 5 10
6 10 5 5 2 2 0 0 1 1 7 7 9
5 9 7 7 1 1 0 0 2 2 4
5 4 2 2 0 0 1 1 7 7 9
3 9 7 7 8 8 13
5 13 8 8 7 7 1...

result:

ok 

Test #9:

score: 0
Accepted
time: 3ms
memory: 3736kb

input:

18 6
0 1
0 2
0 3
1 4
1 5
2 6
2 7
4 12
4 13
6 8
6 9
6 15
6 16
6 17
7 10
7 11
7 14
0 1 2 4 6 7
2 2 7 7 11
3 11 7 7 2 6 17

output:

ATTACK
11
17
16

result:

ok 

Test #10:

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

input:

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

output:

ATTACK
8
7
6

result:

ok 

Test #11:

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

input:

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

output:

ATTACK
3
2

result:

ok 

Test #12:

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

input:

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

output:

ATTACK
7
10
9

result:

ok 

Test #13:

score: 0
Accepted
time: 4ms
memory: 3796kb

input:

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

output:

ATTACK
8
7
6

result:

ok 

Test #14:

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

input:

20 9
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
0 1 2 3 4 5 6 7 8
3 0 1 1 5 5 13
5 13 5 5 1 1 0 3 8 8 19

output:

ATTACK
13
19
9

result:

ok 

Test #15:

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

input:

8 3
0 1
0 2
0 3
1 4
1 5
2 6
2 7
0 1 2
2 0 1 1 4
3 4 1 1 0 2 7

output:

ATTACK
4
7
6

result:

ok 

Test #16:

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

input:

25 12
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
10 22
10 23
10 24
20
17
22
17
13
19
11
24
21
22
21
16
24
18
22
12
14
13
19
23
21
19
11
22
15
24
13
23
19
16
21
11
15
24
12
14
12
15
12
18
22
15
21
24
15
20
24
22
19
18
24
18
11
16
15
11
16
22
13
17
...

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11
6 11 4 4 1 1 0 0 3 3 9 9 20
6 20 9 9 3 3 0 0 2 2 7 7 17
7 17 7 7 2 2 0 0 1 1 4 4 10 10 22
7 22 10 10 4 4 1 1 0 0 2 2 7 7 17
6 17 7 7 2 2 0 0 1 1 5 5 13
6 13 5 5 1 1 0 0 3 3 8 8 19
6 19 8 8 3 3 0 0 1 1 4 4 11
3 11 4 4 10 10 24
7 24 10 10 4 4 1 1 0 0 3 3 9 9 21
7 21 9 ...

result:

ok 

Test #17:

score: 0
Accepted
time: 13ms
memory: 3688kb

input:

29 7
0 1
0 2
0 3
0 21
0 22
2 4
2 5
2 20
3 10
3 11
4 6
4 7
4 16
4 18
4 19
4 23
5 8
5 9
5 14
5 17
5 25
5 26
5 27
11 12
11 13
11 15
11 24
11 28
7
13
20
16
20
21
7
17
12
22
23
1
9
6
25
8
20
22
21
7
19
23
17
12
17
6
26
17
28
15
18
9
17
23
22
13
9
16
27
10
23
19
24
13
16
9
21
13
20
1
6
23
27
21
9
24
18
26...

output:

DEFEND
0 1 2 3 4 5 11
4 1 0 0 2 2 4 4 7
6 7 4 4 2 2 0 0 3 3 11 11 13
5 13 11 11 3 3 0 0 2 2 20
3 20 2 2 4 4 16
3 16 4 4 2 2 20
3 20 2 2 0 0 21
4 21 0 0 2 2 4 4 7
4 7 4 4 2 2 5 5 17
6 17 5 5 2 2 0 0 3 3 11 11 12
4 12 11 11 3 3 0 0 22
4 22 0 0 2 2 4 4 23
4 23 4 4 2 2 0 0 1
4 1 0 0 2 2 5 5 9
4 9 5 5 2 ...

result:

ok 

Test #18:

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

input:

9 3
0 1
0 2
0 3
1 4
1 5
2 6
2 7
2 8
0 1 2
2 0 1 1 5
3 5 1 1 0 2 8

output:

ATTACK
5
8
7

result:

ok 

Test #19:

score: 0
Accepted
time: 19ms
memory: 3840kb

input:

15 7
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
5 14
8
13
7
11
9
6
13
10
6
8
13
10
12
14
6
10
9
12
14
6
7
9
12
8
13
7
10
14
9
14
9
13
6
7
13
11
8
10
13
9
11
7
12
14
9
8
11
14
7
6
13
8
9
7
9
14
8
7
11
9
11
13
10
14
10
8
12
6
14
11
6
13
12
7
14
11
14
10
8
14
9
7
12
14
7
14
6
14
8
6
13
9
1...

output:

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

result:

ok 

Test #20:

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

input:

27 13
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
10 22
10 23
11 24
11 25
11 26
18
16
26
14
18
19
14
23
22
13
15
19
20
22
18
15
18
20
13
23
14
15
20
12
15
24
23
15
13
26
15
23
18
14
12
16
12
18
12
14
17
24
13
14
20
12
25
19
17
25
12
15
25
21
20
15
...

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12
6 12 5 5 1 1 0 0 3 3 8 8 18
6 18 8 8 3 3 0 0 2 2 7 7 16
7 16 7 7 2 2 0 0 1 1 4 4 11 11 26
7 26 11 11 4 4 1 1 0 0 2 2 6 6 14
6 14 6 6 2 2 0 0 3 3 8 8 18
2 18 8 8 19
6 19 8 8 3 3 0 0 2 2 6 6 14
7 14 6 6 2 2 0 0 1 1 4 4 10 10 23
2 23 10 10 22
5 22 10 10 4 4 1 1 5 5 1...

result:

ok 

Test #21:

score: 0
Accepted
time: 3ms
memory: 3796kb

input:

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

output:

ATTACK
6
9
8

result:

ok 

Test #22:

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

input:

31 14
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
10 22
10 23
11 24
11 25
12 26
12 27
13 28
13 29
13 30
0 1 2 3 4 5 6 7 8 9 10 11 12 13
3 0 2 2 6 6 14
5 14 6 6 2 2 0 3 9 9 21
3 21 9 9 3 8 19

output:

ATTACK
14
21
19
18

result:

ok 

Test #23:

score: 0
Accepted
time: 23ms
memory: 3840kb

input:

32 16
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
10 22
10 23
11 24
11 25
12 26
12 27
13 28
13 29
14 30
14 31
25
30
24
19
18
15
22
19
24
16
30
19
29
31
15
27
26
29
31
23
15
18
21
26
30
24
27
22
27
31
18
22
15
24
30
20
26
27
21
18
28
16
21
23
27
25
...

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
7 15 6 6 2 2 0 0 1 1 4 4 11 11 25
8 25 11 11 4 4 1 1 0 0 2 2 6 6 14 14 30
8 30 14 14 6 6 2 2 0 0 1 1 4 4 11 11 24
7 24 11 11 4 4 1 1 0 0 3 3 8 8 19
2 19 8 8 18
6 18 8 8 3 3 0 0 2 2 6 6 15
7 15 6 6 2 2 0 0 1 1 4 4 10 10 22
7 22 10 10 4 4 1 1 0 0 3 3 8 8 19...

result:

ok 

Test #24:

score: 0
Accepted
time: 3ms
memory: 3684kb

input:

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

output:

ATTACK
14
9
8

result:

ok 

Test #25:

score: 0
Accepted
time: 23ms
memory: 3724kb

input:

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

output:

DEFEND
0 1 2 3 4
4 4 1 1 0 0 2 2 6
4 6 2 2 0 0 3 3 9
2 9 3 3 10
4 10 3 3 0 0 1 1 4
4 4 1 1 0 0 3 3 8
4 8 3 3 0 0 2 2 6
4 6 2 2 0 0 1 1 4
4 4 1 1 0 0 2 2 7
4 7 2 2 0 0 1 1 4
4 4 1 1 0 0 3 3 8
4 8 3 3 0 0 1 1 4
2 4 1 1 5
4 5 1 1 0 0 3 3 8
2 8 3 3 10
4 10 3 3 0 0 2 2 6
4 6 2 2 0 0 1 1 5
4 5 1 1 0 0 3 3...

result:

ok 

Test #26:

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

input:

16 7
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
0 1 2 3 4 5 6
2 0 2 2 7
3 7 2 2 0 3 9

output:

ATTACK
7
9
8

result:

ok 

Test #27:

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

input:

19 8
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
7 18
0 1 2 3 4 5 6 7
3 0 2 2 7 7 17
4 17 7 7 2 2 0 3 9

output:

ATTACK
17
9
8

result:

ok 

Test #28:

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

input:

21 9
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
8 20
0 1 2 3 4 5 6 7 8
2 0 3 3 9
4 9 3 3 0 2 7 7 17
3 17 7 7 2 6 15

output:

ATTACK
9
17
15
14

result:

ok 

Test #29:

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

input:

28 13
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
10 22
10 23
11 24
11 25
12 26
12 27
0 1 2 3 4 5 6 7 8 9 10 11 12
3 0 3 3 8 8 19
5 19 8 8 3 3 0 2 7 7 17
3 17 7 7 2 6 15

output:

ATTACK
19
17
15
14

result:

ok 

Test #30:

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

input:

15 7
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
5 14
8
13
7
11
9
6
13
10
6
8
13
10
12
14
6
10
9
12
14
6
7
9
12
8
13
7
10
14
9
14
9
13
6
7
13
11
8
10
13
9
11
7
12
14
9
8
11
14
7
6
13
8
9
7
9
14
8
7
11
9
11
13
10
14
10
8
12
6
14
11
6
13
12
7
14
11
14
10
8
14
9
7
12
14
7
14
6
14
8
6
13
9
1...

output:

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

result:

ok 

Test #31:

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

input:

39 4
0 1
0 2
0 3
0 11
0 12
0 17
0 18
0 22
0 28
0 37
3 4
3 5
3 8
3 13
3 16
3 20
3 23
3 27
3 32
3 33
3 34
5 6
5 7
5 9
5 10
5 14
5 15
5 19
5 21
5 24
5 25
5 26
5 29
5 30
5 31
5 35
5 36
5 38
30
7
24
12
30
23
19
6
35
2
13
38
24
27
9
14
30
24
26
35
19
27
10
1
27
29
7
21
26
23
28
20
31
26
1
28
17
15
1
33
14...

output:

DEFEND
0 1 3 5
4 1 0 0 3 3 5 5 30
2 30 5 5 7
2 7 5 5 24
4 24 5 5 3 3 0 0 12
4 12 0 0 3 3 5 5 30
3 30 5 5 3 3 23
3 23 3 3 5 5 19
2 19 5 5 6
2 6 5 5 35
4 35 5 5 3 3 0 0 2
3 2 0 0 3 3 13
3 13 3 3 5 5 38
2 38 5 5 24
3 24 5 5 3 3 27
3 27 3 3 5 5 9
2 9 5 5 14
2 14 5 5 30
2 30 5 5 24
2 24 5 5 26
2 26 5 5 3...

result:

ok 

Test #32:

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

input:

22 10
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
0 1 2 3 4 5 6 7 8 9
3 0 1 1 4 4 10
5 10 4 4 1 1 0 3 9 9 21
3 21 9 9 3 8 19

output:

ATTACK
10
21
19
18

result:

ok 

Test #33:

score: 0
Accepted
time: 39ms
memory: 3852kb

input:

38 19
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
10 22
10 23
11 24
11 25
12 26
12 27
13 28
13 29
14 30
14 31
15 32
15 33
16 34
16 35
17 36
17 37
20
27
33
20
32
34
29
34
30
27
29
30
29
31
26
18
20
23
18
32
36
34
36
30
37
21
22
32
37
25
18
28
29
33
...

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
4 18 8 8 3 3 9 9 20
7 20 9 9 3 3 0 0 1 1 5 5 12 12 27
8 27 12 12 5 5 1 1 0 0 2 2 6 6 15 15 33
7 33 15 15 6 6 2 2 0 0 3 3 9 9 20
7 20 9 9 3 3 0 0 2 2 6 6 15 15 32
6 32 15 15 6 6 2 2 7 7 16 16 34
8 34 16 16 7 7 2 2 0 0 1 1 5 5 13 13 29
8 29 13 13 5...

result:

ok 

Test #34:

score: 0
Accepted
time: 6ms
memory: 3848kb

input:

37 17
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
10 22
10 23
11 24
11 25
12 26
12 27
13 28
13 29
14 30
14 31
15 32
15 33
16 34
16 35
16 36
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
4 0 2 2 6 6 15 15 33
6 33 15 15 6 6 2 2 0 3 9 9 21
3 21 9 9 3 8 19

output:

ATTACK
33
21
19
18

result:

ok 

Test #35:

score: 0
Accepted
time: 4ms
memory: 3824kb

input:

25 2
0 1
0 2
0 3
0 7
0 8
0 10
0 12
0 15
0 17
0 18
0 21
0 24
1 4
1 5
1 6
1 9
1 11
1 13
1 14
1 16
1 19
1 20
1 22
1 23
0 1
2 0 1 1 20

output:

ATTACK
20
24

result:

ok 

Test #36:

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

input:

20 9
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
0 1 2 3 4 5 6 7 8
3 0 1 1 4 4 10
5 10 4 4 1 1 0 3 8 8 19

output:

ATTACK
10
19
9

result:

ok 

Test #37:

score: 0
Accepted
time: 7ms
memory: 3740kb

input:

35 17
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
10 22
10 23
11 24
11 25
12 26
12 27
13 28
13 29
14 30
14 31
15 32
15 33
15 34
24
27
34
22
19
31
22
25
22
19
23
29
19
28
31
17
28
19
20
25
24
25
23
29
33
21
24
34
25
32
29
33
20
31
28
25
24
28
31
27
...

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
7 16 7 7 2 2 0 0 1 1 4 4 11 11 24
6 24 11 11 4 4 1 1 5 5 12 12 27
8 27 12 12 5 5 1 1 0 0 2 2 6 6 15 15 34
8 34 15 15 6 6 2 2 0 0 1 1 4 4 10 10 22
7 22 10 10 4 4 1 1 0 0 3 3 8 8 19
7 19 8 8 3 3 0 0 2 2 6 6 14 14 31
8 31 14 14 6 6 2 2 0 0 1 1 4 4 10 10 2...

result:

ok 

Test #38:

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

input:

19 8
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
7 18
0 1 2 3 4 5 6 7
2 0 3 3 9
4 9 3 3 0 2 7 7 18
3 18 7 7 2 6 15

output:

ATTACK
9
18
15
14

result:

ok 

Test #39:

score: 0
Accepted
time: 30ms
memory: 3808kb

input:

29 14
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
10 22
10 23
11 24
11 25
12 26
12 27
12 28
15
18
19
23
19
18
20
22
19
20
23
22
19
22
25
23
25
19
26
24
25
21
20
13
27
18
17
15
26
13
18
21
20
22
13
23
28
15
19
28
19
15
17
26
18
17
19
23
19
17
19
25
...

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13
6 13 5 5 1 1 0 0 2 2 6 6 15
6 15 6 6 2 2 0 0 3 3 8 8 18
2 18 8 8 19
7 19 8 8 3 3 0 0 1 1 4 4 10 10 23
7 23 10 10 4 4 1 1 0 0 3 3 8 8 19
2 19 8 8 18
4 18 8 8 3 3 9 9 20
7 20 9 9 3 3 0 0 1 1 4 4 10 10 22
7 22 10 10 4 4 1 1 0 0 3 3 8 8 19
4 19 8 8 3 3 9 9 20
7 20 ...

result:

ok 

Test #40:

score: 0
Accepted
time: 14ms
memory: 3800kb

input:

20 8
0 1
0 2
0 3
1 4
1 5
3 14
3 15
3 16
5 6
5 7
5 18
6 8
6 9
6 17
8 12
8 13
8 19
9 10
9 11
7
18
12
2
11
16
13
16
2
17
13
2
17
19
15
14
19
16
10
16
15
7
4
14
18
12
15
19
10
11
15
18
11
16
13
17
7
19
7
19
2
13
17
10
19
17
15
10
17
11
7
10
18
16
7
11
14
17
11
19
15
18
15
19
2
14
4
12
15
17
2
10
14
17
1...

output:

DEFEND
0 1 2 3 5 6 8 9
4 2 0 0 1 1 5 5 7
2 7 5 5 18
4 18 5 5 6 6 8 8 12
6 12 8 8 6 6 5 5 1 1 0 0 2
6 2 0 0 1 1 5 5 6 6 9 9 11
7 11 9 9 6 6 5 5 1 1 0 0 3 3 16
7 16 3 3 0 0 1 1 5 5 6 6 8 8 13
7 13 8 8 6 6 5 5 1 1 0 0 3 3 16
3 16 3 3 0 0 2
5 2 0 0 1 1 5 5 6 6 17
3 17 6 6 8 8 13
6 13 8 8 6 6 5 5 1 1 0 0...

result:

ok 

Test #41:

score: 0
Accepted
time: 28ms
memory: 3784kb

input:

30 14
0 1
0 2
0 3
1 4
1 5
2 10
2 11
2 28
3 8
3 9
4 16
4 17
5 6
5 7
6 14
6 15
7 20
7 21
8 22
8 23
9 12
9 13
12 18
12 19
20 24
20 25
23 26
23 27
23 29
22
28
21
15
14
10
18
15
21
11
28
15
27
29
10
25
24
27
29
19
10
14
17
24
28
21
25
18
25
29
14
18
10
21
28
16
24
25
17
14
26
11
17
19
25
22
26
18
11
21
2...

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 12 20 23
5 10 2 2 0 0 3 3 8 8 22
5 22 8 8 3 3 0 0 2 2 28
6 28 2 2 0 0 1 1 5 5 7 7 21
4 21 7 7 5 5 6 6 15
2 15 6 6 14
6 14 6 6 5 5 1 1 0 0 2 2 10
6 10 2 2 0 0 3 3 9 9 12 12 18
8 18 12 12 9 9 3 3 0 0 1 1 5 5 6 6 15
4 15 6 6 5 5 7 7 21
6 21 7 7 5 5 1 1 0 0 2 2 11
2 11 2 2 ...

result:

ok 

Test #42:

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

input:

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

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
5 24 11 11 4 4 10 10 22 22 46
4 46 22 22 10 10 23 23 49
5 49 23 23 10 10 4 4 11 11 24
8 24 11 11 4 4 1 1 0 0 3 3 9 9 21 21 44
9 44 21 21 9 9 3 3 0 0 1 1 4 4 10 10 22 22 46
7 46 22 22 10 10 4 4 1 1 5 5 13 13 29
7 29 13 13 5 5 1 1...

result:

ok 

Test #43:

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

input:

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

output:

ATTACK
45
37
33
31
30

result:

ok 

Test #44:

score: 0
Accepted
time: 25ms
memory: 3756kb

input:

37 18
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
10 22
10 23
11 24
11 25
12 26
12 27
13 28
13 29
14 30
14 31
15 32
15 33
16 34
16 35
16 36
19
26
32
19
31
33
28
33
29
26
28
29
28
30
25
17
19
22
17
31
35
33
35
29
36
20
21
31
36
24
17
27
28
32
30
21
...

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
6 17 7 7 2 2 0 0 3 3 8 8 19
7 19 8 8 3 3 0 0 1 1 5 5 12 12 26
8 26 12 12 5 5 1 1 0 0 2 2 6 6 15 15 32
7 32 15 15 6 6 2 2 0 0 3 3 8 8 19
7 19 8 8 3 3 0 0 2 2 6 6 14 14 31
4 31 14 14 6 6 15 15 33
8 33 15 15 6 6 2 2 0 0 1 1 5 5 13 13 28
8 28 13 13 5 5 ...

result:

ok 

Test #45:

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

input:

30 2
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
0 16
0 17
0 18
0 19
0 20
0 21
0 22
0 23
0 24
0 25
0 26
0 27
0 28
0 29
7
20
14
18
21
22
3
26
25
2
4
22
23
25
21
4
21
23
16
26
17
3
23
15
3
27
12
4
17
29
4
12
22
17
15
19
15
21
15
17
5
27
2
17
8
16
13
8
6
14
16
3
28
10
24
4
20
18
5...

output:

DEFEND
0 1
2 1 0 0 7
2 7 0 0 20
2 20 0 0 14
2 14 0 0 18
2 18 0 0 21
2 21 0 0 22
2 22 0 0 3
2 3 0 0 26
2 26 0 0 25
2 25 0 0 2
2 2 0 0 4
2 4 0 0 22
2 22 0 0 23
2 23 0 0 25
2 25 0 0 21
2 21 0 0 4
2 4 0 0 21
2 21 0 0 23
2 23 0 0 16
2 16 0 0 26
2 26 0 0 17
2 17 0 0 3
2 3 0 0 23
2 23 0 0 15
2 15 0 0 3
2 3...

result:

ok 

Test #46:

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

input:

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

output:

ATTACK
33
45
41
39
38

result:

ok 

Test #47:

score: 0
Accepted
time: 3ms
memory: 3824kb

input:

38 18
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
10 22
10 23
11 24
11 25
12 26
12 27
13 28
13 29
14 30
14 31
15 32
15 33
16 34
16 35
17 36
17 37
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
4 0 2 2 6 6 15 15 33
6 33 15 15 6 6 2 2 0 3 9 9 21
3 21 9 ...

output:

ATTACK
33
21
19
18

result:

ok 

Test #48:

score: 0
Accepted
time: 3ms
memory: 3832kb

input:

22 11
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
12
17
12
21
12
14
12
21
16
14
16
10
14
11
18
13
12
15
14
12
11
16
10
17
21
11
19
10
21
19
10
15
21
15
16
18
14
20
19
15
16
12
17
18
20
14
13
18
12
10
11
16
20
14
15
17
11
19
12
11
17
16
19
16
14
15
...

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10
4 10 4 4 1 1 5 5 12
6 12 5 5 1 1 0 0 2 2 7 7 17
6 17 7 7 2 2 0 0 1 1 5 5 12
6 12 5 5 1 1 0 0 3 3 9 9 21
6 21 9 9 3 3 0 0 1 1 5 5 12
6 12 5 5 1 1 0 0 2 2 6 6 14
6 14 6 6 2 2 0 0 1 1 5 5 12
6 12 5 5 1 1 0 0 3 3 9 9 21
6 21 9 9 3 3 0 0 2 2 7 7 16
4 16 7 7 2 2 6 6 14
4 14 6...

result:

ok 

Test #49:

score: 0
Accepted
time: 35ms
memory: 3816kb

input:

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

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
8 26 12 12 5 5 1 1 0 0 2 2 6 6 15 15 32
8 32 15 15 6 6 2 2 0 0 3 3 9 9 21 21 45
6 45 21 21 9 9 3 3 8 8 18 18 39
6 39 18 18 8 8 3 3 9 9 20 20 43
9 43 20 20 9 9 3 3 0 0 1 1 4 4 10 10 22 22 46
2 46 22 22 47
7 47 22 22 10 10 4...

result:

ok 

Test #50:

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

input:

29 13
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
10 22
10 23
11 24
11 25
12 26
12 27
12 28
0 1 2 3 4 5 6 7 8 9 10 11 12
3 0 3 3 8 8 19
5 19 8 8 3 3 0 2 7 7 17
3 17 7 7 2 6 15

output:

ATTACK
19
17
15
14

result:

ok 

Test #51:

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

input:

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

output:

ATTACK
33
45
41
39
38

result:

ok 

Test #52:

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

input:

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

output:

ATTACK
29
45
41
39
38

result:

ok 

Test #53:

score: 0
Accepted
time: 21ms
memory: 3840kb

input:

33 16
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
10 22
10 23
11 24
11 25
12 26
12 27
13 28
13 29
14 30
14 31
14 32
27
29
25
15
21
29
21
15
18
20
21
29
32
30
25
24
32
18
25
18
32
31
25
21
16
21
27
18
29
31
21
15
21
32
30
17
20
19
24
26
21
15
17
21
...

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
7 15 6 6 2 2 0 0 1 1 5 5 12 12 27
4 27 12 12 5 5 13 13 29
6 29 13 13 5 5 1 1 4 4 11 11 25
7 25 11 11 4 4 1 1 0 0 2 2 6 6 15
6 15 6 6 2 2 0 0 3 3 9 9 21
7 21 9 9 3 3 0 0 1 1 5 5 13 13 29
7 29 13 13 5 5 1 1 0 0 3 3 9 9 21
6 21 9 9 3 3 0 0 2 2 6 6 15
6 15 6 ...

result:

ok 

Test #54:

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

input:

22 10
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
0 1 2 3 4 5 6 7 8 9
3 0 2 2 7 7 16
5 16 7 7 2 2 0 3 9 9 21
3 21 9 9 3 8 19

output:

ATTACK
16
21
19
18

result:

ok 

Test #55:

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

input:

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

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
8 27 12 12 5 5 1 1 0 0 2 2 6 6 15 15 33
6 33 15 15 6 6 2 2 7 7 17 17 37
9 37 17 17 7 7 2 2 0 0 1 1 4 4 10 10 22 22 46
9 46 22 22 10 10 4 4 1 1 0 0 2 2 6 6 15 15 32
8 32 15 15 6 6 2 2 0 0 3 3 9 9 20 20 42
9 42 20 20 9 9 ...

result:

ok 

Test #56:

score: 0
Accepted
time: 11ms
memory: 3748kb

input:

41 20
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
10 22
10 23
11 24
11 25
12 26
12 27
13 28
13 29
14 30
14 31
15 32
15 33
16 34
16 35
17 36
17 37
18 38
18 39
18 40
39
23
40
28
32
40
28
37
22
35
28
25
19
22
40
29
24
19
35
37
21
22
27
19
36
30
23
37
...

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
3 19 8 8 18 18 39
8 39 18 18 8 8 3 3 0 0 1 1 4 4 10 10 23
8 23 10 10 4 4 1 1 0 0 3 3 8 8 18 18 40
8 40 18 18 8 8 3 3 0 0 1 1 5 5 13 13 28
8 28 13 13 5 5 1 1 0 0 2 2 6 6 15 15 32
8 32 15 15 6 6 2 2 0 0 3 3 8 8 18 18 40
8 40 18 18 8 8 3 3 0 0 1 ...

result:

ok 

Test #57:

score: 0
Accepted
time: 22ms
memory: 3640kb

input:

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

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
8 23 10 10 4 4 1 1 0 0 3 3 9 9 21 21 45
9 45 21 21 9 9 3 3 0 0 1 1 4 4 10 10 22 22 48
3 48 22 22 10 10 23
8 23 10 10 4 4 1 1 0 0 3 3 9 9 20 20 43
4 43 20 20 9 9 21 21 45
8 45 21 21 9 9 3 3 0 0 1 1 5 5 13 13 28
8 28 13 13 5 5 1 1 0 ...

result:

ok 

Test #58:

score: 0
Accepted
time: 3ms
memory: 3832kb

input:

29 13
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
10 22
10 23
11 24
11 25
12 26
12 27
12 28
0 1 2 3 4 5 6 7 8 9 10 11 12
3 0 3 3 9 9 21
5 21 9 9 3 3 0 2 7 7 17
3 17 7 7 2 6 15

output:

ATTACK
21
17
15
14

result:

ok 

Test #59:

score: 0
Accepted
time: 24ms
memory: 3872kb

input:

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

output:

DEFEND
0 1 2 3 4 5 6 7 9 10 11 12 15
4 7 4 4 3 3 0 0 48
4 48 0 0 3 3 5 5 44
5 44 5 5 3 3 0 0 2 2 35
8 35 2 2 0 0 3 3 4 4 6 6 9 9 11 11 19
7 19 11 11 9 9 6 6 4 4 3 3 0 0 32
5 32 0 0 3 3 4 4 6 6 8
4 8 6 6 9 9 10 10 40
7 40 10 10 9 9 6 6 4 4 3 3 0 0 50
7 50 0 0 3 3 4 4 6 6 9 9 11 11 19
5 19 11 11 9 9 1...

result:

ok 

Test #60:

score: 0
Accepted
time: 39ms
memory: 3760kb

input:

42 21
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
10 22
10 23
11 24
11 25
12 26
12 27
13 28
13 29
14 30
14 31
15 32
15 33
16 34
16 35
17 36
17 37
18 38
18 39
19 40
19 41
40
24
41
29
33
41
29
38
23
36
29
26
20
23
41
30
25
20
36
38
22
23
28
20
37
31
...

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
5 20 9 9 3 3 8 8 19 19 40
8 40 19 19 8 8 3 3 0 0 1 1 4 4 11 11 24
8 24 11 11 4 4 1 1 0 0 3 3 8 8 19 19 41
8 41 19 19 8 8 3 3 0 0 1 1 5 5 13 13 29
8 29 13 13 5 5 1 1 0 0 2 2 6 6 15 15 33
8 33 15 15 6 6 2 2 0 0 3 3 8 8 19 19 41
8 41 19 19 8 8...

result:

ok 

Test #61:

score: 0
Accepted
time: 48ms
memory: 3752kb

input:

30 15
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
10 22
10 23
11 24
11 25
12 26
12 27
13 28
13 29
16
19
20
24
20
19
21
23
20
21
24
23
20
23
26
24
26
20
27
25
26
22
21
14
28
19
18
16
27
14
19
22
21
23
14
24
29
16
20
29
20
16
18
27
19
18
20
24
20
18
...

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
4 14 6 6 2 2 7 7 16
6 16 7 7 2 2 0 0 3 3 8 8 19
4 19 8 8 3 3 9 9 20
7 20 9 9 3 3 0 0 1 1 4 4 11 11 24
7 24 11 11 4 4 1 1 0 0 3 3 9 9 20
4 20 9 9 3 3 8 8 19
4 19 8 8 3 3 9 9 21
7 21 9 9 3 3 0 0 1 1 4 4 10 10 23
7 23 10 10 4 4 1 1 0 0 3 3 9 9 20
2 20 9 9 21
7 ...

result:

ok 

Test #62:

score: 0
Accepted
time: 29ms
memory: 3844kb

input:

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

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
4 22 10 10 4 4 11 11 24
8 24 11 11 4 4 1 1 0 0 3 3 9 9 21 21 45
6 45 21 21 9 9 3 3 8 8 18 18 39
8 39 18 18 8 8 3 3 0 0 2 2 7 7 16 16 34
8 34 16 16 7 7 2 2 0 0 1 1 4 4 11 11 25
8 25 11 11 4 4 1 1 0 0 2 2 6 6 14 14 31
8 31 14 14 6 6 2 2...

result:

ok 

Test #63:

score: 0
Accepted
time: 18ms
memory: 3812kb

input:

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

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
8 29 13 13 5 5 1 1 0 0 2 2 6 6 14 14 31
6 31 14 14 6 6 2 2 7 7 16 16 34
2 34 16 16 35
9 35 16 16 7 7 2 2 0 0 1 1 5 5 12 12 26 26 54
8 54 26 26 12 12 5 5 1 1 4 4 11 11 24 24 50
6 50 24 24 11 11 4 4 10 10 23 23 49
9...

result:

ok 

Test #64:

score: 0
Accepted
time: 20ms
memory: 3836kb

input:

26 12
0 1
0 2
0 3
1 8
1 9
3 4
3 5
4 20
4 21
5 6
5 7
6 12
6 13
6 25
8 10
8 11
9 18
9 19
10 14
10 15
10 24
15 16
15 17
20 22
20 23
16
13
25
11
16
17
11
22
21
7
12
17
18
21
16
12
16
18
7
22
11
12
18
2
12
23
22
12
7
25
12
22
16
11
2
13
2
16
2
11
14
23
7
11
18
2
24
17
14
24
2
12
24
19
18
12
14
12
14
23
1...

output:

DEFEND
0 1 2 3 4 5 6 8 9 10 15 20
6 2 0 0 1 1 8 8 10 10 15 15 16
9 16 15 15 10 10 8 8 1 1 0 0 3 3 5 5 6 6 13
2 13 6 6 25
7 25 6 6 5 5 3 3 0 0 1 1 8 8 11
4 11 8 8 10 10 15 15 16
2 16 15 15 17
4 17 15 15 10 10 8 8 11
7 11 8 8 1 1 0 0 3 3 4 4 20 20 22
3 22 20 20 4 4 21
4 21 4 4 3 3 5 5 7
3 7 5 5 6 6 12...

result:

ok 

Test #65:

score: 0
Accepted
time: 4ms
memory: 3764kb

input:

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

output:

ATTACK
36
45
41
39
38

result:

ok 

Test #66:

score: 0
Accepted
time: 3ms
memory: 3856kb

input:

42 20
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
10 22
10 23
11 24
11 25
12 26
12 27
13 28
13 29
14 30
14 31
15 32
15 33
16 34
16 35
17 36
17 37
18 38
18 39
19 40
19 41
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
4 0 1 1 4 4 11 11 25
7 25 11...

output:

ATTACK
25
41
21
20

result:

ok 

Test #67:

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

input:

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

output:

ATTACK
31
47
41

result:

ok 

Test #68:

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

input:

34 4
0 1
0 2
0 3
0 14
0 16
0 21
0 22
0 23
0 28
0 29
0 30
1 6
1 7
1 15
1 17
1 18
1 27
2 8
2 9
2 11
2 12
2 13
2 19
2 20
2 24
2 31
2 32
2 33
3 4
3 5
3 10
3 25
3 26
0 1 2 3
2 0 2 2 13

output:

ATTACK
13
30

result:

ok 

Test #69:

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

input:

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

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
8 31 14 14 6 6 2 2 0 0 3 3 8 8 19 19 41
9 41 19 19 8 8 3 3 0 0 1 1 4 4 10 10 22 22 46
9 46 22 22 10 10 4 4 1 1 0 0 3 3 8 8 19 19 40
9 40 19 19 8 8 3 3 0 0 1 1 4 4 11 11 25 25 52
9 52 25 25 11 11 4 4 1 1 0 0 ...

result:

ok 

Test #70:

score: 0
Accepted
time: 6ms
memory: 3856kb

input:

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

output:

ATTACK
32
45
41
39
38

result:

ok 

Test #71:

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

input:

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

output:

ATTACK
53
45
41
39
38

result:

ok 

Test #72:

score: 0
Accepted
time: 6ms
memory: 3808kb

input:

39 18
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
10 22
10 23
11 24
11 25
12 26
12 27
13 28
13 29
14 30
14 31
15 32
15 33
16 34
16 35
17 36
17 37
17 38
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
4 0 1 1 4 4 11 11 24
7 24 11 11 4 4 1 1 0 2 7 7 17 1...

output:

ATTACK
24
38
33
31
30

result:

ok 

Test #73:

score: 0
Accepted
time: 37ms
memory: 3748kb

input:

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

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
8 25 11 11 4 4 1 1 0 0 2 2 6 6 15 15 33
8 33 15 15 6 6 2 2 0 0 3 3 9 9 21 21 45
4 45 21 21 9 9 20 20 42
6 42 20 20 9 9 3 3 8 8 19 19 40
8 40 19 19 8 8 3 3 0 0 1 1 5 5 13 13 28
7 28 13 13 5 5 1 1 4 4 10 10 23 23 49
9 49 23 23 ...

result:

ok 

Test #74:

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

input:

37 17
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
10 22
10 23
11 24
11 25
12 26
12 27
13 28
13 29
14 30
14 31
15 32
15 33
16 34
16 35
16 36
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
4 0 2 2 6 6 14 14 30
6 30 14 14 6 6 2 2 0 3 9 9 21
3 21 9 9 3 8 19

output:

ATTACK
30
21
19
18

result:

ok 

Test #75:

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

input:

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

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
8 28 13 13 5 5 1 1 0 0 2 2 7 7 16 16 34
8 34 16 16 7 7 2 2 0 0 3 3 8 8 18 18 38
9 38 18 18 8 8 3 3 0 0 1 1 4 4 10 10 22 22 47
9 47 22 22 10 10 4 4 1 1 0 0 2 2 6 6 15 15 33
8 33 15 15 6 6 2 2 0 0 3 3 9 9 20 20 43
9 43...

result:

ok 

Test #76:

score: 0
Accepted
time: 28ms
memory: 3800kb

input:

33 16
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
10 22
10 23
11 24
11 25
12 26
12 27
13 28
13 29
14 30
14 31
14 32
27
29
25
15
21
29
21
15
18
20
21
29
32
30
25
24
32
18
25
18
32
31
25
21
16
21
27
18
29
31
21
15
21
32
30
17
20
19
24
26
21
15
17
21
...

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
7 15 6 6 2 2 0 0 1 1 5 5 12 12 27
4 27 12 12 5 5 13 13 29
6 29 13 13 5 5 1 1 4 4 11 11 25
7 25 11 11 4 4 1 1 0 0 2 2 6 6 15
6 15 6 6 2 2 0 0 3 3 9 9 21
7 21 9 9 3 3 0 0 1 1 5 5 13 13 29
7 29 13 13 5 5 1 1 0 0 3 3 9 9 21
6 21 9 9 3 3 0 0 2 2 6 6 15
6 15 6 ...

result:

ok 

Test #77:

score: 0
Accepted
time: 4ms
memory: 3796kb

input:

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

output:

ATTACK
71
45
41
39
38

result:

ok 

Test #78:

score: 0
Accepted
time: 32ms
memory: 3780kb

input:

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

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
9 34 16 16 7 7 2 2 0 0 1 1 5 5 13 13 29 29 61
9 61 29 29 13 13 5 5 1 1 0 0 3 3 8 8 18 18 38
9 38 18 18 8 8 3 3 0 0 1 1 5 5 12 12 26 26 55
9 55 26 26 12 12 5 5 1 1 0 0 3 3 9 9 20 20 43
9 43 20 20 9 9...

result:

ok 

Test #79:

score: 0
Accepted
time: 4ms
memory: 3732kb

input:

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

output:

ATTACK
33
45
41
39
38

result:

ok 

Test #80:

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

input:

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

output:

DEFEND
0 1 2 3 4 7
4 4 3 3 0 0 2 2 48
3 48 2 2 0 0 17
3 17 0 0 3 3 46
4 46 3 3 0 0 2 2 48
4 48 2 2 0 0 1 1 64
2 64 1 1 23
4 23 1 1 0 0 2 2 56
4 56 2 2 0 0 1 1 11
5 11 1 1 0 0 2 2 7 7 49
3 49 7 7 2 2 25
4 25 2 2 0 0 3 3 14
4 14 3 3 0 0 2 2 41
3 41 2 2 7 7 40
2 40 7 7 27
3 27 7 7 2 2 12
4 12 2 2 0 0 3...

result:

ok 

Test #81:

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

input:

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

output:

ATTACK
47
65
37
35
34

result:

ok 

Test #82:

score: 0
Accepted
time: 18ms
memory: 3844kb

input:

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

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
8 25 11 11 4 4 1 1 0 0 2 2 6 6 15 15 33
8 33 15 15 6 6 2 2 0 0 3 3 9 9 21 21 45
4 45 21 21 9 9 20 20 42
6 42 20 20 9 9 3 3 8 8 19 19 40
8 40 19 19 8 8 3 3 0 0 1 1 5 5 13 13 28
7 28 13 13 5 5 1 1 4 4 10 10 23 23 49
9 49 23 23 ...

result:

ok 

Test #83:

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

input:

77 10
0 1
0 2
0 3
0 30
0 45
0 50
0 62
0 64
0 71
1 12
1 13
1 22
1 37
1 59
1 63
1 73
3 4
3 5
3 69
3 76
4 6
4 7
4 32
4 36
4 38
4 41
4 57
4 60
4 61
4 67
5 8
5 9
5 25
5 28
5 39
5 53
5 58
5 72
5 74
6 10
6 11
6 31
6 33
6 54
12 18
12 19
12 23
12 27
12 29
12 34
12 40
12 49
12 55
12 56
12 65
13 14
13 15
13 35...

output:

ATTACK
69
71

result:

ok 

Test #84:

score: 0
Accepted
time: 33ms
memory: 3740kb

input:

42 21
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
10 22
10 23
11 24
11 25
12 26
12 27
13 28
13 29
14 30
14 31
15 32
15 33
16 34
16 35
17 36
17 37
18 38
18 39
19 40
19 41
40
24
41
29
33
41
29
38
23
36
29
26
20
23
41
30
25
20
36
38
22
23
28
20
37
31
...

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
5 20 9 9 3 3 8 8 19 19 40
8 40 19 19 8 8 3 3 0 0 1 1 4 4 11 11 24
8 24 11 11 4 4 1 1 0 0 3 3 8 8 19 19 41
8 41 19 19 8 8 3 3 0 0 1 1 5 5 13 13 29
8 29 13 13 5 5 1 1 0 0 2 2 6 6 15 15 33
8 33 15 15 6 6 2 2 0 0 3 3 8 8 19 19 41
8 41 19 19 8 8...

result:

ok 

Test #85:

score: 0
Accepted
time: 18ms
memory: 3760kb

input:

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

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
9 38 18 18 8 8 3 3 0 0 2 2 7 7 16 16 35 35 73
10 73 35 35 16 16 7 7 2 2 0 0 1 1 5 5 12 12 27 27 57
10 57 27 27 12 12 5 5 1 1 0 0 2 2 6 6 14 14 30 30 62
9 62 30 30 14 14 6 6 2 2 0 0 3 3 9...

result:

ok 

Test #86:

score: 0
Accepted
time: 9ms
memory: 3760kb

input:

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

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
7 21 9 9 3 3 0 0 1 1 4 4 10 10 23
6 23 10 10 4 4 1 1 5 5 13 13 28
8 28 13 13 5 5 1 1 0 0 2 2 7 7 16 16 35
6 35 16 16 7 7 2 2 6 6 14 14 31
6 31 14 14 6 6 2 2 7 7 16 16 35
4 35 16 16 7 7 17 17 36
8 36 17 17 7 7 2 2 0 0 1 1 4 4 10 10 23
8 2...

result:

ok 

Test #87:

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

input:

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

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
4 31 14 14 6 6 15 15 33
9 33 15 15 6 6 2 2 0 0 1 1 5 5 13 13 29 29 60
9 60 29 29 13 13 5 5 1 1 0 0 2 2 6 6 15 15 33
9 33 15 15 6 6 2 2 0 0 1 1 4 4 11 11 25 25 53
8 53 25 25 11 11 4 4 1 1 5 5 12 12 27 27 56
9...

result:

ok 

Test #88:

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

input:

83 2
0 1
0 2
0 3
0 6
0 7
0 10
0 11
0 13
0 18
0 20
0 25
0 26
0 32
0 33
0 34
0 35
0 36
0 38
0 39
0 43
0 45
0 46
0 47
0 49
0 50
0 54
0 55
0 56
0 57
0 60
0 61
0 64
0 65
0 66
0 68
0 70
0 71
0 72
0 73
0 77
0 79
0 80
0 81
2 4
2 5
2 8
2 9
2 12
2 14
2 15
2 16
2 17
2 19
2 21
2 22
2 23
2 24
2 27
2 28
2 29
2 30...

output:

ATTACK
27
81

result:

ok 

Test #89:

score: 0
Accepted
time: 25ms
memory: 3852kb

input:

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

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
9 40 19 19 8 8 3 3 0 0 2 2 7 7 17 17 37 37 76
6 76 37 37 17 17 7 7 16 16 35 35 72
8 72 35 35 16 16 7 7 2 2 6 6 14 14 30 30 63
10 63 30 30 14 14 6 6 2 2 0 0 1 1 4 4 10 10 22 22 47
8...

result:

ok 

Test #90:

score: 0
Accepted
time: 4ms
memory: 3708kb

input:

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

output:

ATTACK
42
37
33
31
30

result:

ok 

Test #91:

score: 0
Accepted
time: 36ms
memory: 3788kb

input:

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

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
6 32 15 15 6 6 2 2 7 7 16 16 34
9 34 16 16 7 7 2 2 0 0 1 1 5 5 13 13 29 29 61
9 61 29 29 13 13 5 5 1 1 0 0 2 2 7 7 16 16 34
9 34 16 16 7 7 2 2 0 0 1 1 5 5 12 12 26 26 54
4 54 26 26 12 12 27 27 57
8 57 27 ...

result:

ok 

Test #92:

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

input:

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

output:

ATTACK
42
77
69
65
63
62

result:

ok 

Test #93:

score: 0
Accepted
time: 6ms
memory: 3848kb

input:

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

output:

ATTACK
26
44
41
39
38

result:

ok 

Test #94:

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

input:

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

output:

ATTACK
23
56
55

result:

ok 

Test #95:

score: 0
Accepted
time: 9ms
memory: 3856kb

input:

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

output:

ATTACK
50
78
69
65
63
62

result:

ok 

Test #96:

score: 0
Accepted
time: 7ms
memory: 3836kb

input:

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

output:

ATTACK
24
43
41
39
38

result:

ok 

Test #97:

score: 0
Accepted
time: 12ms
memory: 3760kb

input:

42 21
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
10 22
10 23
11 24
11 25
12 26
12 27
13 28
13 29
14 30
14 31
15 32
15 33
16 34
16 35
17 36
17 37
18 38
18 39
19 40
19 41
40
24
41
29
33
41
29
38
23
36
29
26
20
23
41
30
25
20
36
38
22
23
28
20
37
31
...

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
5 20 9 9 3 3 8 8 19 19 40
8 40 19 19 8 8 3 3 0 0 1 1 4 4 11 11 24
8 24 11 11 4 4 1 1 0 0 3 3 8 8 19 19 41
8 41 19 19 8 8 3 3 0 0 1 1 5 5 13 13 29
8 29 13 13 5 5 1 1 0 0 2 2 6 6 15 15 33
8 33 15 15 6 6 2 2 0 0 3 3 8 8 19 19 41
8 41 19 19 8 8...

result:

ok 

Test #98:

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

input:

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

output:

ATTACK
40
37
33
31
30

result:

ok 

Test #99:

score: 0
Accepted
time: 24ms
memory: 3784kb

input:

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

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
9 38 18 18 8 8 3 3 0 0 2 2 7 7 16 16 35 35 73
10 73 35 35 16 16 7 7 2 2 0 0 1 1 5 5 12 12 27 27 57
10 57 27 27 12 12 5 5 1 1 0 0 2 2 6 6 14 14 30 30 62
9 62 30 30 14 14 6 6 2 2 0 0 3 3 9...

result:

ok 

Test #100:

score: 0
Accepted
time: 10ms
memory: 3812kb

input:

4 3
0 1
0 2
0 3
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
3
1
...

output:

DEFEND
0 1 2
2 1 0 0 3
2 3 0 0 1
2 1 0 0 3
2 3 0 0 1
2 1 0 0 3
2 3 0 0 1
2 1 0 0 3
2 3 0 0 1
2 1 0 0 3
2 3 0 0 1
2 1 0 0 3
2 3 0 0 1
2 1 0 0 3
2 3 0 0 1
2 1 0 0 3
2 3 0 0 1
2 1 0 0 3
2 3 0 0 1
2 1 0 0 3
2 3 0 0 1
2 1 0 0 3
2 3 0 0 1
2 1 0 0 3
2 3 0 0 1
2 1 0 0 3
2 3 0 0 1
2 1 0 0 3
2 3 0 0 1
2 1 0 0...

result:

ok 

Test #101:

score: 0
Accepted
time: 4ms
memory: 3888kb

input:

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

output:

ATTACK
44
66
37
35
34

result:

ok 

Test #102:

score: 0
Accepted
time: 33ms
memory: 3876kb

input:

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

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
9 33 15 15 6 6 2 2 0 0 1 1 5 5 13 13 29 29 60
9 60 29 29 13 13 5 5 1 1 0 0 2 2 7 7 17 17 37
9 37 17 17 7 7 2 2 0 0 1 1 5 5 12 12 26 26 54
9 54 26 26 12 12 5 5 1 1 0 0 3 3 9 9 20 20 42
9 42 20 20 9 9 3 ...

result:

ok 

Test #103:

score: 0
Accepted
time: 19ms
memory: 3864kb

input:

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

output:

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

result:

ok 

Test #104:

score: 0
Accepted
time: 6ms
memory: 3744kb

input:

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

output:

ATTACK
44
33

result:

ok 

Test #105:

score: 0
Accepted
time: 7ms
memory: 3760kb

input:

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

output:

ATTACK
49
45
41
39
38

result:

ok 

Test #106:

score: 0
Accepted
time: 21ms
memory: 3796kb

input:

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

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
9 38 18 18 8 8 3 3 0 0 2 2 7 7 16 16 35 35 73
10 73 35 35 16 16 7 7 2 2 0 0 1 1 5 5 12 12 27 27 57
10 57 27 27 12 12 5 5 1 1 0 0 2 2 6 6 14 14 30 30 62
9 62 30 30 14 14 6 6 2 2 0 0 3 3 9...

result:

ok 

Test #107:

score: 0
Accepted
time: 4ms
memory: 3824kb

input:

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

output:

ATTACK
1
3

result:

ok