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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <time.h>

#define x first
#define y second

#define FOUND "TAK"
#define NOT_FOUND "NIE"

std::vector<long int> calculate(std::vector<std::pair<int,
        std::pair<long int, long int> > > &pts) {
   
    std::vector<long int> sides;

    std::sort(pts.begin(), pts.end(),
            [](std::pair<int, std::pair<long int, long int> > a,
                std::pair<int, std::pair<long int, long int> > b) {
                return (a.y.y == b.y.y ? a.y.x < b.y.x : a.y.y < b.y.y);
            });

    int l = 0, r = 0, t = 0, b = 0;
    for (int i = 0; i < pts.size(); ++i) {
        l = (pts[l].y.x <= pts[i].y.x ? l : i);
        r = (pts[r].y.x >= pts[i].y.x ? r : i);
        t = (pts[t].y.y >= pts[i].y.y ? t : i);
        b = (pts[b].y.y <= pts[i].y.y ? b : i);
    }

    if (l != b) {
        return sides;
    } else {
        while (sides.size() < pts.size()) {
            sides.push_back(1 + rand() % 5);
        }
    }

    return sides;
}

int main () {
    srand(time(NULL));
    std::vector<std::pair<int, std::pair <long int, long int> > > points;
    int t;
    
    std::cin >> t;

    while (t--) {
        int n;
        
        std::cin >> n;
        points.resize(n);
        
        for (int i = 0; i < n; ++i) {
            points[i].x = i;
            std::cin >> points[i].y.x >> points[i].y.y;
        }

        std::vector<long int> sides = calculate(points);

        if (sides.empty()) {
            std::cout << NOT_FOUND << std::endl;
        } else {
            std::cout << FOUND;
            for (auto &s : sides) {
                std::cout << " " << s;
            }
            std::cout << std::endl;
        }
    }
    return 0;
}