Submission details
Task:Zig Zag
Sender:aalto26jw_006
Submission time:2026-11-11 17:06:51 +0200
Language:C++ (C++23)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails
#7ACCEPTED0.00 sdetails
#8ACCEPTED0.00 sdetails
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails
#14ACCEPTED0.00 sdetails
#15ACCEPTED0.00 sdetails
#16ACCEPTED0.00 sdetails
#17ACCEPTED0.00 sdetails
#18ACCEPTED0.00 sdetails
#19ACCEPTED0.00 sdetails
#20ACCEPTED0.00 sdetails
#21ACCEPTED0.00 sdetails
#22ACCEPTED0.00 sdetails
#23ACCEPTED0.00 sdetails
#24ACCEPTED0.00 sdetails
#25ACCEPTED0.00 sdetails
#26ACCEPTED0.00 sdetails
#27ACCEPTED0.00 sdetails
#28ACCEPTED0.00 sdetails
#29ACCEPTED0.00 sdetails
#30ACCEPTED0.00 sdetails
#31ACCEPTED0.00 sdetails
#32ACCEPTED0.00 sdetails
#33ACCEPTED0.00 sdetails
#34ACCEPTED0.00 sdetails
#35ACCEPTED0.00 sdetails
#36ACCEPTED0.00 sdetails
#37ACCEPTED0.00 sdetails
#38ACCEPTED0.00 sdetails
#39ACCEPTED0.00 sdetails
#40ACCEPTED0.00 sdetails
#41ACCEPTED0.00 sdetails
#42ACCEPTED0.00 sdetails
#43ACCEPTED0.00 sdetails
#44ACCEPTED0.00 sdetails
#45ACCEPTED0.00 sdetails
#46ACCEPTED0.00 sdetails
#47ACCEPTED0.00 sdetails
#48ACCEPTED0.00 sdetails
#49ACCEPTED0.01 sdetails
#50ACCEPTED0.01 sdetails
#51ACCEPTED0.01 sdetails
#52ACCEPTED0.01 sdetails
#53ACCEPTED0.01 sdetails
#54ACCEPTED0.01 sdetails
#55ACCEPTED0.01 sdetails
#56ACCEPTED0.01 sdetails
#57ACCEPTED0.01 sdetails
#58ACCEPTED0.01 sdetails
#59ACCEPTED0.04 sdetails
#60ACCEPTED0.04 sdetails
#61ACCEPTED0.04 sdetails
#62ACCEPTED0.04 sdetails
#63ACCEPTED0.04 sdetails
#64ACCEPTED0.18 sdetails
#65ACCEPTED0.18 sdetails
#66ACCEPTED0.18 sdetails
#67ACCEPTED0.18 sdetails
#68ACCEPTED0.18 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:536:24: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'std::tuple_element<0, std::tuple<long long int> >::type' {aka 'long long int'} [-Wsign-compare]
  536 |         if (out.size() < n){
      |             ~~~~~~~~~~~^~~

Code

#include <iostream>
#include <vector>
#include <functional>
#include <set>
#include <algorithm>
#include <stack>
#include <unordered_map>
#include <map>
#include <iomanip>
#include <limits>
#include <queue>
#include <math.h>
#include <bits/stdc++.h>
 
typedef long long LL;
typedef std::tuple<LL>          TUP1LL;
typedef std::tuple<LL,LL>       TUP2LL;
typedef std::tuple<LL,LL,LL>    TUP3LL;
typedef std::tuple<LL,LL,LL,LL> TUP4LL;

 
std::tuple<LL> readLL1(){
    LL a;
    std::cin >> a;
    return {a};
}

std::tuple<LL,LL> readLL2(){
    LL a, b;
    std::cin >> a >> b;
    return {a,b};
}

std::tuple<LL,LL,LL> readLL3(){
    LL a, b, c;
    std::cin >> a >> b >> c;
    return {a,b,c};
}
std::tuple<LL,LL,LL,LL> readLL4(){
    LL a, b, c, d;
    std::cin >> a >> b >> c >> d;
    return {a,b,c,d};
}
 
std::vector<LL> readVecLL(LL n){
    std::vector<LL> arr(n);
    for (LL i = 0; i < n; i++){
        LL a;
        std::cin >> a;
        arr[i] = a;
    }
    return arr;
}

std::string readStr(){
    std::string a;
    std::cin >> a;
    return a;
}

std::vector<std::string> readVecStr(LL n){
    std::vector<std::string> arr(n);
    for (LL i = 0; i < n; i++){
        std::string a;
        std::cin >> a;
        arr[i] = a;
    }
    return arr;
}
 
std::vector<std::tuple<LL,LL>> readVecTup2(LL n){
    std::vector<std::tuple<LL,LL>> arr(n);
    for (LL i = 0; i < n; i++){
        arr[i] = readLL2();
    }
    return arr;
}
 
std::vector<std::tuple<LL,LL,LL>> readVecTup3(LL n){
    std::vector<std::tuple<LL,LL,LL>> arr(n);
    for (LL i = 0; i < n; i++){
        arr[i] = readLL3();
    }
    return arr;
}
std::vector<std::tuple<double,double,double>> readVecTup3Dup(LL n){
    std::vector<std::tuple<double,double,double>> arr(n);
    for (LL i = 0; i < n; i++){
        double a, b, c;
        std::cin >> a;
        std::cin >> b;
        std::cin >> c;
        arr[i] = {a,b,c};
    }
    return arr;
}
std::vector<std::tuple<LL,LL,LL,LL>> readVecTup4(LL n){
    std::vector<std::tuple<LL,LL,LL,LL>> arr(n);
    for (LL i = 0; i < n; i++){
        arr[i] = readLL4();
    }
    return arr;
}
 
void printNewLine(){std::cout << "\n";}
template<typename T, typename... Ts>
std::tuple<Ts...> tail(std::tuple<T,Ts...> as){
    return std::apply([](T &a, Ts... b){return std::make_tuple(b...);},as);
}
 
template<typename T>
void print(T a){std::cout << std::setprecision(19) << a;}
template<typename... T>
void println(T... a);
 
template<typename T, typename Ts>
void print(std::tuple<T,Ts> a){
    print(std::get<0>(a));
    print(" ");
    print(std::get<1>(a));
}
 
template<typename T, typename... Ts>
void print(std::tuple<T,Ts...> a){
    print(std::get<0>(a));
    print(" ");
    print(tail(a));
}
 
template<typename T>
void print(const std::vector<T> &arr, LL width = -1){
    if (width == -1) width = arr.size();
    for (LL i = 0; i < (LL)arr.size(); i++){
        print(arr[i]);
        if (i+1 == (LL)arr.size()) continue;
        if ((i%width) == width-1) printNewLine();
        if ((i%width) != width-1) print(" ");
    }    
}
template<typename... T>
void println(T... a){print(a...);printNewLine();}
 
 
 
template<typename T>
void sorted(std::vector<T> &arr){
    std::sort(arr.begin(),arr.end(),[](const T &a, const T &b){ return a < b; });
}

template<typename T>
std::set<T> toSet(const std::vector<T> &vec){
    std::set<T> c;
    for (T a : vec){ c.emplace(a);}
    return c;
}
 
template<typename T, typename N>
std::vector<N> map(const std::vector<T> &a, const std::function<N(T)> &transform){
    std::vector<N> b(a.size());
    LL i = 0;
    for (T x : a){
        b[i] = transform(x);
        i++;
    }
    return b;
}
 
template<typename N, typename M, typename R>
std::vector<R> zip(const std::vector<N> &a, const  std::vector<M> &b, const std::function<R(N,M)> &transform){
    LL n = std::min(a.size(),b.size());
    std::vector<R> res(n);
    for (LL i = 0; i < n; i++){
        res[i] = transform(a[i],b[i]);
    }
    return res;
}
 
template<typename T, typename N>
std::vector<N> convertVec(const std::vector<T> &a){
    std::vector<N> b(a.size());
    LL i = 0;
    for (T x : a){
        b[i] = x;
        i++;
    }
    return b;
}

template<typename T>
std::vector<T> reverse(const std::vector<T> &a){
    std::vector<T> b(a.size());
    LL i = 0;
    for (T x : a){
        b[a.size()-1-i] = x;
        i++;
    }
    return b;
}

template<typename T, typename R>
R reduce(const std::vector<T> &arr, R init, const std::function<R(const R,const T)> &transform){
    R current = init;
    for (LL idx = 0; idx < (LL)arr.size(); idx++){
        current = transform(current,arr[idx]);
    };
    return current;
}
template<typename T>
T max(const std::vector<T> &arr){return reduce(arr, arr[0], static_cast<std::function<T(const T,const T)>>(static_cast<const T& (*)(const T&, const T&)>(std::max<T>)));}
template<typename T>
T min(const std::vector<T> &arr){return reduce(arr, arr[0], static_cast<std::function<T(const T,const T)>>(static_cast<const T& (*)(const T&, const T&)>(std::min<T>)));}

template<typename T>
std::function<T(const T,const T)> add(){return [](T a,T b){return a+b;};}
template<typename T>
std::function<T(const T,const T)> modAdd(T mod){return [mod](T a,T b){return (((a+b)%mod)+mod)%mod;};}
template<typename T, typename R>
std::function<R(const R,const T)> mulAdd(R mul){return [mul](R a,T b){return a+b*mul;};}
template<typename T>
T sum(const std::vector<T> &arr){return reduce(arr, 0, add<T>());}
template<typename T>
T avg(const std::vector<T> &arr){return reduce(arr, 0.0, mulAdd<double,T>(1.0/arr.size()));}

template<typename T>
T binarySearch(T min, T max, const std::function<bool(T)> &leq){
    if (min == max) return max;
    T guess = (min+max)/2;
    if (leq(guess)){
        return binarySearch(min,guess,leq);
    }else{
        return binarySearch(guess+1,max,leq);
    }
}

template<typename T>
T binarySearchDecending(T min, T max, const std::function<bool(T)> &leq){
    std::function<bool(T)> gt = [leq](T x){
        return !leq(x);
    };
    return binarySearch(min,max+1, gt)-1;
}

template<typename T>
std::vector<T> cloneVec(std::vector<T> a){return a;}

template<typename T>
std::vector<T> padding(const std::vector<T> &initial, T num, LL start, LL end){
    std::vector<T> arr(start+initial.size()+end);
    for (LL i = 0; i < start; i++){
        arr[i] = num;
    }
    for (LL i = 0; i < (LL)initial.size(); i++){
        arr[start+i] = initial[i];
    }
    for (LL i = 0; i < end; i++){
        arr[start+initial.size()+i] = num;
    }
    return arr;
}

template<typename T>
LL findMax(LL start, LL end, const std::function<T(LL)> &maxHeuristic){
    T initialGuess = maxHeuristic(start);
    LL index = start;
    for (LL i = start; i <= end; i++){
        if (initialGuess < maxHeuristic(i)){
            initialGuess = maxHeuristic(i);
            index = i;
        }
    }
    return index;
}

template<typename T>
void operateOnMax(LL start, LL end, const std::function<T(LL)> &maxHeuristic, const std::function<void(LL)> &found){
    found(findMax(start,end,maxHeuristic));
}

template<typename T>
void stackOperate(std::vector<T> init, const std::function<std::vector<T>(T)> operate){
    std::stack<T> stack;
    for (auto x : init){
        stack.push(x);
    }
    while (!stack.empty()){
        T next = stack.top();
        stack.pop();
        std::vector<T> nextSteps = operate(next);
        for (T a : nextSteps){
            stack.push(a);
        }
    }
}

template<typename T>
void queueOperate(std::vector<T> init, const std::function<std::vector<T>(T)> operate){
    std::queue<T> que;
    for (auto x : init){
        que.push(x);
    }
    while (!que.empty()){
        T next = que.front();
        que.pop();
        std::vector<T> nextSteps = operate(next);
        for (T a : nextSteps){
            que.push(a);
        }
    }
}

template<typename T>
void priorityQueueOperate(std::vector<T> init, const std::function<std::vector<T>(T)> operate){
    std::priority_queue<T> que;
    for (auto x : init){
        que.push(x);
    }
    while (!que.empty()){
        T next = que.top();
        que.pop();
        std::vector<T> nextSteps = operate(next);
        for (T a : nextSteps){
            que.push(a);
        }
    }
}
 
template<typename T>
void recursiveVectorSplit(LL start, LL end, LL distl, LL distr, const std::function<T(LL)> &maxHeuristic, const std::function<void(LL)> &found){
    if (start == end){
        return found(start);
    }else if (end < start){
        return;
    }
    std::tuple<LL,LL> range = {start,end};
    std::function<std::vector<std::tuple<LL,LL>>(std::tuple<LL,LL>)> splitter = [distl, distr,&maxHeuristic,&found](std::tuple<LL,LL> range){
        auto [start,end] = range;
        LL idx = findMax(start, end, maxHeuristic);
        found(idx);
        std::vector<std::tuple<LL,LL>> next;
        if (idx+distl+1 <= end){
            next.push_back({idx+distl+1,end});
        }
        if (start <= idx-distr-1){
            next.push_back({start, idx-distr-1});
        }
        return next;
    };
    stackOperate({range},splitter);
}
 
 
template<typename T>
std::vector<T> dynamicallyComputableList(LL n, std::function<T(std::vector<T>&,LL)> next){
    std::vector<T> arr(n);
    for (LL i = 0; i < n; i++){
        arr[i] = next(arr,i);
    }
    return arr;
}
template<typename T>
LL indexOfBinarySearch(const std::vector<T> &arr, const T &find){
    return binarySearch((LL)0,(LL)arr.size()-1,(std::function<bool(LL)>)[&arr, &find](LL guess){return find <= arr[guess];});
}

template<typename T>
std::unordered_map<T, LL> indexCompress(const std::vector<T> &arr){
    std::unordered_map<T, LL> compressed;
    LL i = 0;
    for (T x : arr){
        if (compressed.find(x) != compressed.end()) compressed[x] = i++;
    }
    return compressed;
}   

template<typename... Ts>
std::tuple<std::vector<std::tuple<LL,Ts...>>, std::vector<LL>> edgeIndexing(int n, std::vector<std::tuple<LL,Ts...>> edges){
    sorted(edges);
    std::vector<LL> edgeIndex(n+1);
    {
        LL j = 0;
        for (LL i = 0; i < (LL)edges.size(); i++) {
            auto a = std::get<0>(edges[i]);
            while (j <= a){
                edgeIndex[j++] = i;
            }
        }
        while (j < n){
            edgeIndex[j++] = edges.size();
        }
        edgeIndex[n] = edges.size(); 
    }
    return {edges,edgeIndex};
}


template<typename T>
std::tuple<std::vector<T>, std::vector<LL>> shortestPathDirected(const LL n, std::vector<std::tuple<LL, LL, T>> edgesInit, LL start){
    //assumes all paths are between 0 <= c < n
    //assumes 0 indexing
    std::vector<LL> path(n);
    std::vector<bool> edgeUpdated(n);
    std::vector<T> distance(n);
    for (LL i = 0; i < n; i++) path[i] = i;
    for (LL i = 0; i < n; i++) edgeUpdated[i] = true;
    edgeUpdated[start] = false;
    for (LL i = 0; i < n; i++) distance[i] = std::numeric_limits<T>::max()/4;
    distance[start] = 0;
    auto [edges,edgeIndex] = edgeIndexing(n,edgesInit);
    std::function<std::vector<std::tuple<LL,LL>>(std::tuple<LL,LL>)> func = [&distance,&edgeIndex,&edges,&path,&edgeUpdated](std::tuple<LL,LL> propagateW){
        auto& [weight,propagate] = propagateW;
        std::vector<std::tuple<LL,LL>> next;
        if (distance[propagate] != -weight) return next;
        if (edgeUpdated[propagate]) return next;
        for (LL i = edgeIndex[propagate]; i < edgeIndex[propagate+1]; i++){
            auto& [a, b, w] = edges[i];
            if (distance[a]+w < distance[b]){
            //if (std::min(distance[a],w) > distance[b]){
                next.push_back({-(distance[a]+w),b});
                //next.push_back({std::min(distance[a],w),b});
                distance[b] = std::min(distance[a],w);
                path[b] = a;
                edgeUpdated[b] = false;
            }
        }
        edgeUpdated[propagate] = true;
        return next;
    };
    priorityQueueOperate((std::vector<std::tuple<LL,LL>>){{0,start}},func);
    //for (LL i = 0; i < n; i++) {
    //    bool changed = false;
    //    for (auto& e : edges) {
    //        auto& [a, b, w] = e;
    //        if (!changed) {changed = (distance[b] != std::min(distance[b], distance[a]+w));}
    //        if (distance[a]+w < distance[b]){
    //            distance[b] = distance[a]+w;
    //            path[b] = a;
    //        }
    //    }
    //    if (!changed) break;
    //    if (changed && i == n){
    //        return std::tuple((std::vector<T>){},(std::vector<LL>){});
    //    }
    //}
    return std::tuple(distance,path);
}
 
std::vector<LL> pathFromPathMap(std::vector<LL> &map, LL goal){
    std::stack<LL> fullPath;
    fullPath.push(goal);
    while (map[fullPath.top()] != fullPath.top()){
        fullPath.push(map[fullPath.top()]);
    }
    std::vector<LL> p;
    while (!fullPath.empty()){
        p.push_back(fullPath.top());
        fullPath.pop();
    }
    return p;
}
 
 
template<typename T>
std::tuple<std::vector<T>, std::vector<LL>> shortestPath(const LL n, std::vector<std::tuple<LL, LL, T>> &edgesMessy, LL start){
    std::vector<std::tuple<LL, LL, T>> edges;
    for (auto e : edgesMessy){
        auto [a,b,t] = e;
        edges.push_back({a,b,t});
        edges.push_back({b,a,t});
    }
    return shortestPathDirected(n, edges, start);
}



template<typename T>
std::vector<T> range(const std::vector<T> &a, LL from, LL to){
    std::vector<T> b;
    for (LL i = from; i < to; i++){
        b.push_back(a[i]);
    }
    return b;
}

template<typename T>
bool forall(const std::vector<T> &a, std::function<bool(T)> &test){
    bool res = true;
    for (auto v : a){
        res = res & test(v);
    }
    return res;
}



int main() {
    auto [n] = readLL1();
    auto points = readVecTup2(n);
    //std::vector<TUP3LL> list;
    //int i = 0;
    //for (auto p : points){
    //    auto [x,y] = p;
    //    i++;
    //    list.push_back({x,y,i});
    //}
    //sorted(list);
    //std::vector<LL> out;
    //std::set<LL> chosen;
    //out.push_back(std::get<2>(list[0]));
    //out.push_back(std::get<2>(list[n-1]));
    //chosen.emplace(std::get<2>(list[0]));
    //chosen.emplace(std::get<2>(list[n-1]));
    //TUP2LL dir = {std::get<0>(list[n-1])-std::get<0>(list[0]),std::get<1>(list[n-1])-std::get<1>(list[0])};
    //double maxDist = 0;
    //auto [ix,iy] = points[out[out.size()-1]];
    //for (int i = 0; i < n; i++){
    //    if (chosen.find(i) != chosen.end()) continue;
    //    auto [cx,cy] = points[out[out.size()-1]];
    //    if ()
    //    out[i] = std::get<2>(list[ i%2 == 1? n - (i+1)/2 : i/2]);
    //}
    std::vector<LL> out = {0};
    std::set<LL> chosen = {0};
    for (int j = 0; j < n; j++){
        double maxDist = 0;
        auto [x,y] = points[out[out.size()-1]];
        LL best;
        for (int i = 0; i < n; i++){
            if (chosen.find(i) != chosen.end()) continue;
            auto [cx,cy] = points[i];
            double distance = (x-cx)*(double)(x-cx)+(y-cy)*(double)(y-cy);
            if (maxDist < distance){
                best = i;
                maxDist = distance;
            }
        }
        if (out.size() < n){
            chosen.emplace(best);
            out.push_back(best);
        }
    }
    for (int i = 0; i < n; i++) out[i]++;

    println(out);
    return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
2
2 5
8 9

correct output
1 2 

user output
1 2

Test 2

Verdict: ACCEPTED

input
3
3 9
8 7
9 9

correct output
1 3 2 

user output
1 3 2

Test 3

Verdict: ACCEPTED

input
3
6 10
8 7
9 4

correct output
1 3 2 

user output
1 3 2

Test 4

Verdict: ACCEPTED

input
3
1 2
2 6
9 9

correct output
1 3 2 

user output
1 3 2

Test 5

Verdict: ACCEPTED

input
3
3 4
6 1
6 4

correct output
1 2 3 

user output
1 2 3

Test 6

Verdict: ACCEPTED

input
3
2 9
3 2
6 9

correct output
1 2 3 

user output
1 2 3

Test 7

Verdict: ACCEPTED

input
4
2 10
6 5
7 1
9 3

correct output
1 3 2 4 

user output
1 3 2 4

Test 8

Verdict: ACCEPTED

input
4
1 5
2 3
3 8
8 5

correct output
1 4 2 3 

user output
1 4 2 3

Test 9

Verdict: ACCEPTED

input
4
2 7
5 4
7 3
10 1

correct output
1 4 2 3 

user output
1 4 2 3

Test 10

Verdict: ACCEPTED

input
4
1 5
4 3
4 8
10 3

correct output
1 4 3 2 

user output
1 4 3 2

Test 11

Verdict: ACCEPTED

input
4
1 9
4 7
4 8
5 5

correct output
1 4 3 2 

user output
1 4 3 2

Test 12

Verdict: ACCEPTED

input
4
1 6
3 2
4 9
9 4

correct output
1 4 3 2 

user output
1 4 3 2

Test 13

Verdict: ACCEPTED

input
4
3 1
5 10
6 3
9 8

correct output
1 2 3 4 

user output
1 2 3 4

Test 14

Verdict: ACCEPTED

input
4
1 7
6 6
8 6
9 3

correct output
1 4 2 3 

user output
1 4 2 3

Test 15

Verdict: ACCEPTED

input
4
4 10
6 1
7 4
9 3

correct output
1 2 4 3 

user output
1 2 4 3

Test 16

Verdict: ACCEPTED

input
4
1 9
6 4
7 3
8 3

correct output
1 4 2 3 

user output
1 4 2 3

Test 17

Verdict: ACCEPTED

input
4
1 2
6 10
7 3
10 5

correct output
1 4 2 3 

user output
1 4 2 3

Test 18

Verdict: ACCEPTED

input
4
4 7
9 5
9 9
10 5

correct output
1 4 3 2 

user output
1 4 3 2

Test 19

Verdict: ACCEPTED

input
5
5 7
6 6
6 9
7 9
...

correct output
1 5 2 4 3 

user output
1 5 2 4 3

Test 20

Verdict: ACCEPTED

input
5
1 2
2 3
4 10
5 10
...

correct output
1 5 2 4 3 

user output
1 5 2 4 3

Test 21

Verdict: ACCEPTED

input
5
1 10
5 2
5 4
5 5
...

correct output
1 2 5 3 4 

user output
1 2 5 3 4

Test 22

Verdict: ACCEPTED

input
5
3 2
6 1
6 6
8 9
...

correct output
1 4 2 3 5 

user output
1 4 2 3 5

Test 23

Verdict: ACCEPTED

input
5
6 2
7 6
8 7
10 9
...

correct output
1 5 2 4 3 

user output
1 5 2 4 3

Test 24

Verdict: ACCEPTED

input
5
3 1
3 4
5 1
9 9
...

correct output
1 5 3 4 2 

user output
1 5 3 4 2

Test 25

Verdict: ACCEPTED

input
5
1 4
2 10
4 3
9 1
...

correct output
1 5 4 2 3 

user output
1 5 4 2 3

Test 26

Verdict: ACCEPTED

input
5
1 3
5 10
8 4
8 5
...

correct output
1 5 2 3 4 

user output
1 5 2 3 4

Test 27

Verdict: ACCEPTED

input
5
3 5
6 9
9 1
9 4
...

correct output
1 5 2 3 4 

user output
1 5 2 3 4

Test 28

Verdict: ACCEPTED

input
5
1 4
2 1
2 4
5 1
...

correct output
1 5 2 3 4 

user output
1 5 2 3 4

Test 29

Verdict: ACCEPTED

input
10
4 5
5 3
5 7
6 6
...

correct output
1 9 5 10 7 2 8 6 3 4 

user output
1 9 5 10 7 2 8 6 3 4

Test 30

Verdict: ACCEPTED

input
10
1 2
1 4
2 3
2 4
...

correct output
1 10 2 8 3 6 4 9 7 5 

user output
1 10 2 8 3 6 4 9 7 5

Test 31

Verdict: ACCEPTED

input
10
1 10
3 5
3 7
4 2
...

correct output
1 9 8 4 10 5 3 6 2 7 

user output
1 9 8 4 10 5 3 6 2 7

Test 32

Verdict: ACCEPTED

input
10
1 1
2 1
3 2
3 3
...

correct output
1 8 2 10 3 9 5 6 7 4 

user output
1 8 2 10 3 9 5 6 7 4

Test 33

Verdict: ACCEPTED

input
10
1 7
3 2
3 10
5 7
...

correct output
1 8 3 5 10 2 9 4 7 6 

user output
1 8 3 5 10 2 9 4 7 6

Test 34

Verdict: ACCEPTED

input
10
2 9
3 1
3 4
3 10
...

correct output
1 5 10 2 9 3 4 8 6 7 

user output
1 5 10 2 9 3 4 8 6 7

Test 35

Verdict: ACCEPTED

input
10
1 4
2 10
4 3
4 5
...

correct output
1 10 6 2 9 8 3 7 4 5 

user output
1 10 6 2 9 8 3 7 4 5

Test 36

Verdict: ACCEPTED

input
10
1 3
1 5
3 1
5 6
...

correct output
1 10 2 8 5 3 9 6 4 7 

user output
1 10 2 8 5 3 9 6 4 7

Test 37

Verdict: ACCEPTED

input
10
1 7
3 5
5 5
5 8
...

correct output
1 8 5 10 2 9 7 6 4 3 

user output
1 8 5 10 2 9 7 6 4 3

Test 38

Verdict: ACCEPTED

input
10
1 4
2 1
2 4
3 2
...

correct output
1 10 5 7 3 9 2 6 4 8 

user output
1 10 5 7 3 9 2 6 4 8

Test 39

Verdict: ACCEPTED

input
100
5041736 157240647
20175393 348043754
21461600 42077569
21590319 177103472
...

correct output
1 95 3 98 4 99 10 81 29 7 96 8...

user output
1 95 3 98 4 99 10 81 29 7 96 8...

Test 40

Verdict: ACCEPTED

input
100
122816 137572579
3081988 829722338
16987929 288837678
20795114 89789519
...

correct output
1 94 4 90 14 97 21 96 3 99 8 9...

user output
1 94 4 90 14 97 21 96 3 99 8 9...

Test 41

Verdict: ACCEPTED

input
100
13977261 381987546
27435119 390118206
27838076 590195590
29208319 801689376
...

correct output
1 100 9 94 14 77 12 99 2 97 7 ...

user output
1 100 9 94 14 77 12 99 2 97 7 ...

Test 42

Verdict: ACCEPTED

input
100
24822301 241650433
25750352 822299809
32079340 156090008
55262494 100450154
...

correct output
1 100 4 99 3 87 11 77 12 64 20...

user output
1 100 4 99 3 87 11 77 12 64 20...

Test 43

Verdict: ACCEPTED

input
100
5539596 212262730
9648746 657694080
20427661 42713839
23212898 52113136
...

correct output
1 94 3 91 4 88 7 81 14 75 28 6...

user output
1 94 3 91 4 88 7 81 14 75 28 6...

Test 44

Verdict: ACCEPTED

input
100
1763267 741881723
6157975 278203924
21895078 521944783
24624220 604717980
...

correct output
1 100 16 97 24 77 23 94 15 70 ...

user output
1 100 16 97 24 77 23 94 15 70 ...

Test 45

Verdict: ACCEPTED

input
100
39308105 838098679
44426603 836947476
51198751 708680148
63176060 437557708
...

correct output
1 99 2 96 5 100 3 97 11 71 25 ...

user output
1 99 2 96 5 100 3 97 11 71 25 ...

Test 46

Verdict: ACCEPTED

input
100
26735342 806125341
42569672 497138595
70798611 724056782
77364316 450297483
...

correct output
1 97 6 100 3 98 10 94 25 78 41...

user output
1 97 6 100 3 98 10 94 25 78 41...

Test 47

Verdict: ACCEPTED

input
100
8921056 150015577
14394691 72903212
22850648 457512559
27825976 466880371
...

correct output
1 81 5 99 2 83 11 54 96 12 88 ...

user output
1 81 5 99 2 83 11 54 96 12 88 ...

Test 48

Verdict: ACCEPTED

input
100
4900393 476861950
8745675 461759249
11139168 391337048
37347058 286446807
...

correct output
1 97 6 87 24 84 17 93 25 94 5 ...

user output
1 97 6 87 24 84 17 93 25 94 5 ...

Test 49

Verdict: ACCEPTED

input
200
5041736 157240647
12577900 821317682
20175393 348043754
21461600 42077569
...

correct output
1 186 4 183 15 195 5 196 20 19...

user output
1 186 4 183 15 195 5 196 20 19...

Test 50

Verdict: ACCEPTED

input
200
122816 137572579
3081988 829722338
8592846 688876470
16987929 288837678
...

correct output
1 186 6 200 9 182 31 177 29 19...

user output
1 186 6 200 9 182 31 177 29 19...

Test 51

Verdict: ACCEPTED

input
200
5007418 457386905
9071363 177024747
11005899 132698
13977261 381987546
...

correct output
1 197 3 180 5 195 6 199 19 166...

user output
1 197 3 180 5 195 6 199 19 166...

Test 52

Verdict: ACCEPTED

input
200
24822301 241650433
25750352 822299809
27410345 98925543
32079340 156090008
...

correct output
1 198 5 187 3 197 6 170 19 151...

user output
1 198 5 187 3 197 6 170 19 151...

Test 53

Verdict: ACCEPTED

input
200
4210032 63222017
5539596 212262730
9648746 657694080
17149028 626575097
...

correct output
1 191 6 186 7 181 13 159 11 16...

user output
1 191 6 186 7 181 13 159 11 16...

Test 54

Verdict: ACCEPTED

input
200
1763267 741881723
6157975 278203924
13795513 320861635
21895078 521944783
...

correct output
1 200 28 182 41 187 40 192 18 ...

user output
1 200 28 182 41 187 40 192 18 ...

Test 55

Verdict: ACCEPTED

input
200
8476925 141485410
8505126 166581265
12461681 74039645
15361440 452562087
...

correct output
1 192 3 196 18 186 2 177 28 18...

user output
1 192 3 196 18 186 2 177 28 18...

Test 56

Verdict: ACCEPTED

input
200
1991410 698069978
7670036 191583196
8822402 685559485
11360091 77004696
...

correct output
1 198 6 192 14 199 7 200 3 194...

user output
1 198 6 192 14 199 7 200 3 194...

Test 57

Verdict: ACCEPTED

input
200
4472345 555680129
7737822 978991670
8921056 150015577
14394691 72903212
...

correct output
1 191 2 188 24 177 22 200 8 18...

user output
1 191 2 188 24 177 22 200 8 18...

Test 58

Verdict: ACCEPTED

input
200
366794 310416436
4900393 476861950
8745675 461759249
11139168 391337048
...

correct output
1 197 13 193 7 187 39 172 32 1...

user output
1 197 13 193 7 187 39 172 32 1...

Test 59

Verdict: ACCEPTED

input
1000
4982121 854709206
5051980 969850608
6610770 110841534
7756396 54539209
...

correct output
1 933 2 989 10 938 11 977 45 9...

user output
1 933 2 989 10 938 11 977 45 9...

Test 60

Verdict: ACCEPTED

input
1000
692639 597387122
870901 527592476
3407540 258414659
3706190 578214810
...

correct output
1 987 30 901 17 997 81 942 82 ...

user output
1 987 30 901 17 997 81 942 82 ...

Test 61

Verdict: ACCEPTED

input
1000
52022 846049438
151015 375423447
798369 995844330
1351954 659601047
...

correct output
1 997 3 944 28 957 6 998 23 90...

user output
1 997 3 944 28 957 6 998 23 90...

Test 62

Verdict: ACCEPTED

input
1000
1296052 600889338
1645696 768715355
2692564 473274745
3499475 38421523
...

correct output
1 991 59 989 9 958 13 954 80 9...

user output
1 991 59 989 9 958 13 954 80 9...

Test 63

Verdict: ACCEPTED

input
1000
1126577 499684443
1256131 518722321
5616399 179078305
7506590 750644416
...

correct output
1 993 32 934 82 982 65 913 29 ...

user output
1 993 32 934 82 982 65 913 29 ...

Test 64

Verdict: ACCEPTED

input
2000
40804 71218080
59095 459895029
423473 9299604
685308 815211163
...

correct output
1 1989 3 1970 60 1943 34 1941 ...

user output
1 1989 3 1970 60 1943 34 1941 ...

Test 65

Verdict: ACCEPTED

input
2000
1408858 277110806
2161135 364884754
2812466 979975883
4200717 277590999
...

correct output
1 1975 45 1898 108 1892 134 19...

user output
1 1975 45 1898 108 1892 134 19...

Test 66

Verdict: ACCEPTED

input
2000
1709459 406796814
1857492 878587442
2005566 168482214
3426573 973328677
...

correct output
1 2000 31 1928 12 1994 41 1940...

user output
1 2000 31 1928 12 1994 41 1940...

Test 67

Verdict: ACCEPTED

input
2000
554335 614887580
2154289 832986059
2227123 110013552
2614185 311227898
...

correct output
1 1977 10 1981 33 1908 34 1978...

user output
1 1977 10 1981 33 1908 34 1978...

Test 68

Verdict: ACCEPTED

input
2000
890991 100455230
1036021 428733862
1938719 436899661
2001873 863975225
...

correct output
1 1998 24 1999 48 1994 53 1950...

user output
1 1998 24 1999 48 1994 53 1950...