QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#830532	#8359. travel	ZnPdCo	100 ✓	376ms	237924kb	C++14	6.7kb	2024-12-24 20:26:32	2024-12-24 20:26:45

Judging History

This is the latest submission verdict.

[2024-12-24 20:26:45]
Judged

Verdict: 100
Time: 376ms
Memory: 237924kb

Show

[2024-12-24 20:26:32]
Submitted

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 5;
int T, n, k, op;
int head[N], nxt[2 * N], to[2 * N], cnt;
int dep[N], sz[N], weight[N], leaf[N], rt;
int f[N][18], dad[N], top[N], dfn[N], idx, dis[N];
void addEdge(int u, int v) {
    nxt[++cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
}
int find(int x) {
    if(dad[x] == x) return x;
    return dad[x] = find(dad[x]);
}
void merge(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return;
    dad[x] = y;
}
void getCentroid(int u, int fa) {
    sz[u] = 1, weight[u] = 0;
    for(int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if(v == fa) continue;
        getCentroid(v, u);
        sz[u] += sz[v], weight[u] = max(weight[u], sz[v]);
    }
    weight[u] = max(weight[u], n - sz[u]);
    if(weight[u] <= n / 2) rt = u;
}
int LCA(int u, int v) {
    if(dep[u] < dep[v]) swap(u, v);
    for(int i = 17; i >= 0; i--) {
        if(dep[f[u][i]] >= dep[v]) u = f[u][i];
    }
    if(u == v) return u;
    for(int i = 17; i >= 0; i--) {
        if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
    }
    return f[u][0];
}
void dfs1(int u, int fa) {
    dfn[u] = ++idx, dep[u] = dep[fa] + 1, sz[u] = 1, f[u][0] = fa;
    for(int i = 1; i <= 17; i++) f[u][i] = f[f[u][i - 1]][i - 1];
    for(int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if(v == fa) continue;
        dis[v] = dis[u] + 1;
        dfs1(v, u);
        sz[u] += sz[v];
    }
}
int dfs2(int u, int fa, int &lst_leaf, priority_queue<tuple<int, int, int>> &q, int t) {
    leaf[u] = u;
    top[u] = t;
    for(int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if(v == fa) continue;
        leaf[u] = dfs2(v, u, lst_leaf, q, t);
    }
    if(leaf[u] == u) {
        if(lst_leaf != -1) q.emplace(2 * (dep[LCA(u, lst_leaf)] - 1), u, lst_leaf);
        lst_leaf = u;
    }
    else q.emplace(2 * (dep[u] - 1), u, leaf[u]);
    return leaf[u];
}
priority_queue<tuple<int, int, int>> path[N];
void run(int k, int up, bool type) {
    priority_queue<pair<int, int>> q;
    for(int i = head[rt]; i; i = nxt[i]) {
        int v = to[i], lst_leaf = -1;
        path[v] = {};
        dfs2(v, rt, lst_leaf, path[v], v);
        q.emplace(path[v].size(), v);
    }
    top[rt] = 0;
    int now = up;
    while(k != now) {
        auto [sz, u] = q.top();
        q.pop();
        while(now - get<0>(path[u].top()) < k) path[u].pop();
        now -= get<0>(path[u].top());
        merge(get<1>(path[u].top()), get<2>(path[u].top()));
        path[u].pop();
        q.emplace(path[u].size(), u);
    }
    vector<vector<int>> res1(n + 1), res2(n + 1);
    for(int i = 1; i <= n; i++) res1[find(i)].push_back(i);
    for(int i = 1; i <= n; i++) if(res1[i].size()) sort(res1[i].begin(), res1[i].end(), [](const auto &x, const auto &y) {return dfn[x] < dfn[y];});
    for(int i = 1; i <= n; i++) if(res1[i].size()) res2[top[res1[i][0]]].push_back(i);
    for(int i = 1; i <= n; i++) if(res2[i].size()) sort(res2[i].begin(), res2[i].end(), [&](const auto &x, const auto &y) {return (dep[res1[x][0]] == 2) < (dep[res1[y][0]] == 2);});
    q = {};
    for(int i = 1; i <= n; i++) if(res2[i].size()) q.emplace(res2[i].size(), i);
    // type0:根节点放在最后，第一个是根节点的儿子，正常做就好
    // type1:第一个和最后一个都是根节点的儿子，先使得第一个和第二个满足，然后位移一下

    vector<int> ans1, ans2;
    while(!q.empty()) {
        auto [sz, u] = q.top();
        q.pop();
        ans1.push_back(res2[u].back());
        res2[u].pop_back();
        if(!q.empty()) {
            auto [sz1, u1] = q.top();
            q.pop();
            ans1.push_back(res2[u1].back());
            res2[u1].pop_back();
            if(res2[u1].size()) q.emplace(sz1 - 1, u1);
        }
        if(res2[u].size()) q.emplace(sz - 1, u);
    }
    ans1.push_back(rt);

    switch(type) {
        case 0:
        for(int i : ans1) {
            for(int j : res1[i]) {
                ans2.push_back(j);
            }
        }
        break;
        case 1:
        reverse(res1[ans1[0]].begin(), res1[ans1[0]].end());
        ans1.push_back(*ans1.begin());
        ans1.erase(ans1.begin());
        for(int i : ans1) {
            for(int j : res1[i]) {
                ans2.push_back(j);
            }
        }
        break;
    }

    for(int i : ans2) printf("%lld ", i);
    printf("\n");
}
void dfs3(int u, int fa) {
    if(dis[u] > dis[rt]) rt = u;
    for(int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if(v == fa) continue;
        dis[v] = dis[u] + 1;
        dfs3(v, u);
    }
}
void dfs4(int u, int fa, int end) {
    if(u != end) printf("%lld ", u);
    for(int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if(v == fa) continue;
        if(dfn[v] <= dfn[end] && dfn[v] + sz[v] - 1 >= dfn[end]) continue;
        dfs4(v, u, end);
    }
    for(int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if(v == fa) continue;
        if(dfn[v] <= dfn[end] && dfn[v] + sz[v] - 1 >= dfn[end]) dfs4(v, u, end);
    }
    if(u == end) printf("%lld ", u);
}
void solve() {
    scanf("%lld%lld%lld", &n, &k, &op);
    for(int i = 1; i <= n; i++) head[i] = 0, dad[i] = i; cnt = 0, idx = 0;
    for(int i = 1; i < n; i++) {
        int u, v;
        scanf("%lld%lld", &u, &v);
        addEdge(u, v), addEdge(v, u);
    }
    getCentroid(1, 0);
    dfs1(rt, 0);
    int up = 0;
    for(int i = 1; i <= n; i++) up += (dep[i] - 1) * 2;
    switch(op) {
        case 1:
        if(n == 1) {
            if(k == 0) printf("1\n");
            else printf("-1\n");
            return;
        } else if(n == 2) {
            if(k == 1) printf("1 2\n");
            else printf("-1\n");
            return;
        } else if(k < 2 * (n - 1)) {
            dis[rt] = 0, dfs3(rt, 0);
            dis[rt] = 0, idx = 0, dfs1(rt, 0);
            int end = 0;
            for(int i = 1; i <= n; i++) if(dis[i] == 2 * (n - 1) - k) end = i;
            if(!end) return (void)(printf("-1\n"));
            dfs4(rt, 0, end);
            return (void)(printf("\n"));
        }
        if(k >= up) return (void)(printf("-1\n"));
        if(k % 2 == 1) {
            run(k + 1, up, 0);
        } else if(k % 2 == 0) {
            run(k + 2, up, 1);
        }
        break;
        case 2:
        if(k < 2 * (n - 1) || k > up || k % 2 == 1) return (void)(printf("-1\n"));
        run(k, up, 0);
        break;
    }
}
signed main() {
	// freopen("dis.in", "r", stdin);
	// freopen("dis.out", "w", stdout);
    scanf("%lld", &T);
    while(T--) solve();
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 2

Accepted

Test #1:

score: 2

Accepted

time: 5ms

memory: 20328kb

input:

output:

result:

ok Accepted.

Subtask #2:

score: 4

Accepted

Test #2:

score: 4

Accepted

time: 0ms

memory: 40592kb

input:

output:

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

result:

ok Accepted.

Test #3:

score: 4

Accepted

time: 0ms

memory: 40580kb

input:

output:

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

result:

ok Accepted.

Test #4:

score: 4

Accepted

time: 7ms

memory: 40388kb

input:

output:

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

result:

ok Accepted.

Test #5:

score: 4

Accepted

time: 0ms

memory: 40228kb

input:

output:

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

result:

ok Accepted.

Test #6:

score: 4

Accepted

time: 3ms

memory: 40788kb

input:

output:

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

result:

ok Accepted.

Test #7:

score: 4

Accepted

time: 0ms

memory: 41364kb

input:

output:

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

result:

ok Accepted.

Test #8:

score: 4

Accepted

time: 0ms

memory: 38764kb

input:

output:

result:

ok Accepted.

Subtask #3:

score: 8

Accepted

Dependency #2:

100%

Accepted

Test #9:

score: 8

Accepted

time: 5ms

memory: 41808kb

input:

output:

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

result:

ok Accepted.

Test #10:

score: 8

Accepted

time: 0ms

memory: 40312kb

input:

output:

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

result:

ok Accepted.

Test #11:

score: 8

Accepted

time: 4ms

memory: 40816kb

input:

output:

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

result:

ok Accepted.

Test #12:

score: 8

Accepted

time: 3ms

memory: 40760kb

input:

output:

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

result:

ok Accepted.

Test #13:

score: 8

Accepted

time: 0ms

memory: 40928kb

input:

output:

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

result:

ok Accepted.

Test #14:

score: 8

Accepted

time: 4ms

memory: 40556kb

input:

output:

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

result:

ok Accepted.

Test #15:

score: 8

Accepted

time: 0ms

memory: 38820kb

input:

output:

result:

ok Accepted.

Subtask #4:

score: 14

Accepted

Test #16:

score: 14

Accepted

time: 4ms

memory: 41516kb

input:

output:

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

result:

ok Accepted.

Test #17:

score: 14

Accepted

time: 0ms

memory: 40472kb

input:

output:

9 8 7 6 5 4 3 2 1 
4 6 7 8 9 3 2 1 5 
9 8 7 6 5 4 3 2 1 
-1
6 4 8 9 2 7 3 1 5 
-1
-1
6 7 8 9 4 3 2 1 5 
-1
-1
-1
-1
-1
-1
6 4 9 3 8 2 7 1 5 
-1
-1
-1
-1
-1
-1
-1
-1
-1
9 8 7 6 5 4 3 2 1 
-1
-1
-1
-1
-1
-1
10 9 8 7 6 5 4 3 2 1 
-1
9 8 7 6 5 4 3 2 1 
-1
6 4 1 8 9 3 7 2 5 
-1
-1
6 3 8 9 10 2 7 1 5 4 
-...

result:

ok Accepted.

Test #18:

score: 14

Accepted

time: 0ms

memory: 39320kb

input:

output:

result:

ok Accepted.

Test #19:

score: 14

Accepted

time: 0ms

memory: 41840kb

input:

output:

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

result:

ok Accepted.

Test #20:

score: 14

Accepted

time: 4ms

memory: 41860kb

input:

output:

44 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 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 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 43 48 42 47 41 45 46 
47 49 57 58 59 60 61 62 63 64 65 66 67...

result:

ok Accepted.

Test #21:

score: 14

Accepted

time: 0ms

memory: 40888kb

input:

output:

384 383 382 381 380 379 378 377 376 375 374 373 372 371 370 369 368 367 366 365 364 363 362 361 360 359 358 357 356 355 354 353 352 351 350 349 348 347 346 345 344 343 342 341 340 339 338 337 336 335 334 333 332 331 330 329 328 327 326 325 324 323 322 321 320 319 318 317 316 315 314 313 312 311 310 ...

result:

ok Accepted.

Test #22:

score: 14

Accepted

time: 4ms

memory: 42076kb

input:

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

output:

190 188 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 220 104 221 105 222 106 223 107 224 108 225 109 226 110 227 111 228 112 229 113...

result:

ok Accepted.

Test #23:

score: 14

Accepted

time: 0ms

memory: 41508kb

input:

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

output:

968 966 1088 707 1089 709 1090 710 1091 711 1092 712 1093 713 1094 714 1095 715 1096 716 1097 717 1099 718 1100 719 1101 720 1102 721 1103 722 1104 723 1105 724 1106 725 1107 726 1108 727 1109 728 1098 730 1064 708 1065 682 1066 685 1067 686 1068 687 1069 688 1070 689 1071 690 1072 691 1073 692 1074...

result:

ok Accepted.

Test #24:

score: 14

Accepted

time: 0ms

memory: 41472kb

input:

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

output:

959 961 958 962 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 ...

result:

ok Accepted.

Test #25:

score: 14

Accepted

time: 0ms

memory: 42636kb

input:

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

output:

919 325 1227 323 1226 322 1225 321 1224 320 1223 319 1222 318 1221 317 1220 316 1219 315 1218 314 1217 313 1216 312 1215 311 1213 310 1212 309 1211 308 1210 307 1209 306 1208 305 1207 304 1206 303 1205 302 1204 301 1203 300 1202 299 1201 297 1214 324 1255 353 1254 351 1253 350 1252 349 1251 348 1250...

result:

ok Accepted.

Test #26:

score: 14

Accepted

time: 2ms

memory: 41120kb

input:

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

output:

926 928 554 1120 552 1119 551 1118 550 1117 549 1116 548 1115 547 1114 546 1112 545 1111 544 1110 543 1109 542 1108 541 1107 540 1106 539 1105 537 1113 553 1138 572 1137 570 1136 569 1135 568 1134 567 1133 566 1132 565 1131 564 1121 538 1129 562 1128 561 1127 560 1126 559 1125 558 1124 557 1123 556 ...

result:

ok Accepted.

Subtask #5:

score: 10

Accepted

Dependency #4:

100%

Accepted

Test #27:

score: 10

Accepted

time: 121ms

memory: 38696kb

input:

output:

result:

ok Accepted.

Test #28:

score: 10

Accepted

time: 150ms

memory: 101504kb

input:

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

output:

46523 46521 56417 26708 56418 26710 56419 26711 56420 26712 56421 26713 56422 26714 56423 26715 56424 26716 56425 26717 56426 26718 56427 26719 56428 26720 56429 26721 56431 26722 56432 26723 56433 26724 56434 26725 56435 26726 56436 26727 56437 26728 56438 26729 56439 26730 56440 26731 56441 26732 ...

result:

ok Accepted.

Test #29:

score: 10

Accepted

time: 171ms

memory: 222036kb

input:

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

output:

240924 240926 240897 240896 240895 240894 240893 240892 240891 240890 240889 240888 240887 240886 240885 240884 240883 240882 240881 240880 240879 240878 240877 240876 240875 240874 240873 240872 240871 240870 240869 240868 240867 240866 240865 240864 240863 240862 240861 240860 240859 240858 240857...

result:

ok Accepted.

Test #30:

score: 10

Accepted

time: 193ms

memory: 237924kb

input:

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

output:

247382 247380 293867 154427 293866 154425 293865 154424 293864 154423 293863 154422 293862 154421 293861 154420 293859 154419 293858 154418 293857 154417 293856 154416 293855 154415 293854 154414 293853 154413 293852 154412 293860 154410 293884 154426 293883 154444 293882 154442 293881 154441 293880...

result:

ok Accepted.

Test #31:

score: 10

Accepted

time: 191ms

memory: 237384kb

input:

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

output:

245324 245322 295023 145937 295022 145935 295021 145934 295020 145933 295019 145932 295018 145931 295017 145930 295016 145929 295014 145928 295013 145927 295012 145926 295011 145925 295010 145924 295009 145923 295008 145922 295007 145921 295015 145919 295041 145936 295040 145955 295039 145953 295038...

result:

ok Accepted.

Test #32:

score: 10

Accepted

time: 162ms

memory: 230812kb

input:

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

output:

228005 228007 101856 291093 101854 291092 101853 291091 101852 291090 101851 291089 101850 291088 101849 291087 101848 291086 101847 291085 101846 291084 101845 291082 101844 291081 101843 291080 101842 291079 101841 291078 101840 291077 101839 291076 101838 291075 101837 291074 101836 291073 101835...

result:

ok Accepted.

Test #33:

score: 10

Accepted

time: 69ms

memory: 40216kb

input:

output:

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 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 49 
-1
-1
-1
49 30...

result:

ok Accepted.

Test #34:

score: 10

Accepted

time: 116ms

memory: 40496kb

input:

output:

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

result:

ok Accepted.

Test #35:

score: 10

Accepted

time: 118ms

memory: 41792kb

input:

output:

117 115 140 90 139 88 138 87 137 86 136 85 135 84 134 83 133 82 132 81 131 80 130 79 128 78 127 77 126 76 125 75 124 74 123 73 122 72 121 71 120 70 119 69 118 114 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22...

result:

ok Accepted.

Test #36:

score: 10

Accepted

time: 136ms

memory: 46380kb

input:

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

output:

1212 1210 1510 639 1509 637 1508 636 1507 635 1506 634 1505 633 1504 632 1503 631 1502 630 1501 629 1500 628 1499 627 1497 626 1496 625 1495 624 1494 623 1493 622 1492 621 1491 620 1490 619 1489 618 1488 617 1487 616 1486 615 1485 614 1498 612 1537 638 1536 666 1535 664 1534 663 1533 662 1532 661 15...

result:

ok Accepted.

Test #37:

score: 10

Accepted

time: 133ms

memory: 58404kb

input:

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

output:

4585 4583 5173 3381 5174 3383 5175 3384 5176 3385 5177 3386 5178 3387 5179 3388 5180 3389 5181 3390 5182 3391 5183 3392 5184 3393 5186 3394 5187 3395 5188 3396 5189 3397 5190 3398 5191 3399 5192 3400 5193 3401 5194 3402 5195 3403 5196 3404 5197 3405 5198 3406 5185 3408 5145 3382 5146 3353 5147 3355 ...

result:

ok Accepted.

Test #38:

score: 10

Accepted

time: 139ms

memory: 59288kb

input:

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

output:

12052 12054 5330 15424 5328 15423 5327 15422 5326 15421 5325 15420 5324 15419 5323 15418 5322 15417 5321 15415 5320 15414 5319 15413 5318 15412 5317 15411 5316 15410 5315 15409 5314 15408 5313 15407 5311 15416 5329 15444 5350 15443 5348 15442 5347 15441 5346 15440 5345 15439 5344 15438 5343 15437 53...

result:

ok Accepted.

Test #39:

score: 10

Accepted

time: 157ms

memory: 70072kb

input:

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

output:

24170 24168 24171 24156 24147 24146 24145 24144 24143 24142 24141 24140 24139 24138 24137 24136 24135 24134 24133 24132 24131 24130 24129 24128 24127 24126 24125 24124 24123 24122 24121 24120 24119 24118 24117 24116 24115 24114 24113 24112 24111 24110 24109 24108 24107 24106 24105 24104 24103 24102 ...

result:

ok Accepted.

Test #40:

score: 10

Accepted

time: 154ms

memory: 69428kb

input:

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

output:

24207 24205 31150 10301 31151 10303 31152 10304 31153 10305 31154 10306 31155 10307 31156 10308 31157 10309 31158 10310 31160 10311 31161 10312 31162 10313 31163 10314 31164 10315 31165 10316 31166 10317 31167 10318 31168 10319 31159 10321 31130 10302 31131 10281 31132 10283 31133 10284 31134 10285 ...

result:

ok Accepted.

Test #41:

score: 10

Accepted

time: 157ms

memory: 96700kb

input:

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

output:

45598 45596 60696 15420 60695 15418 60694 15417 60693 15416 60692 15415 60691 15414 60690 15413 60689 15412 60688 15411 60687 15410 60685 15409 60684 15408 60683 15407 60682 15406 60681 15405 60680 15404 60679 15403 60678 15402 60677 15401 60676 15400 60686 15398 60718 15419 60717 15442 60716 15440 ...

result:

ok Accepted.

Subtask #6:

score: 12

Accepted

Dependency #3:

100%

Accepted

Test #42:

score: 12

Accepted

time: 0ms

memory: 40460kb

input:

output:

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

result:

ok Accepted.

Test #43:

score: 12

Accepted

time: 8ms

memory: 40496kb

input:

output:

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

result:

ok Accepted.

Test #44:

score: 12

Accepted

time: 3ms

memory: 39824kb

input:

output:

result:

ok Accepted.

Test #45:

score: 12

Accepted

time: 0ms

memory: 41792kb

input:

output:

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

result:

ok Accepted.

Test #46:

score: 12

Accepted

time: 3ms

memory: 41568kb

input:

output:

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

result:

ok Accepted.

Test #47:

score: 12

Accepted

time: 0ms

memory: 41736kb

input:

output:

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

result:

ok Accepted.

Test #48:

score: 12

Accepted

time: 3ms

memory: 40308kb

input:

output:

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

result:

ok Accepted.

Test #49:

score: 12

Accepted

time: 3ms

memory: 40688kb

input:

output:

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

result:

ok Accepted.

Test #50:

score: 12

Accepted

time: 0ms

memory: 39916kb

input:

output:

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

result:

ok Accepted.

Test #51:

score: 12

Accepted

time: 0ms

memory: 40416kb

input:

output:

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

result:

ok Accepted.

Test #52:

score: 12

Accepted

time: 4ms

memory: 40472kb

input:

output:

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

result:

ok Accepted.

Subtask #7:

score: 18

Accepted

Dependency #4:

100%

Accepted

Dependency #6:

100%

Accepted

Test #53:

score: 18

Accepted

time: 4ms

memory: 39528kb

input:

output:

result:

ok Accepted.

Test #54:

score: 18

Accepted

time: 0ms

memory: 41616kb

input:

output:

264 21 103 88 109 90 110 98 111 101 137 284 93 203 154 246 114 104 125 105 177 127 213 28 106 129 108 134 112 143 113 144 118 145 121 147 122 190 123 149 87 150 130 151 131 157 139 158 140 165 153 174 155 175 159 178 161 179 164 82 95 180 166 183 167 186 169 187 171 148 128 4 5 367 10 8 117 18 9 119...

result:

ok Accepted.

Test #55:

score: 18

Accepted

time: 0ms

memory: 41324kb

input:

1
1981 59778 1
581 1357
1357 1114
1319 822
822 1185
1143 365
619 708
708 1424
1424 1489
1489 1936
1936 1740
1789 1497
1497 387
387 1272
1272 485
1448 418
418 893
1011 1305
1305 176
1593 915
915 1594
1594 1432
1432 1794
1794 837
17 704
704 1542
1270 802
802 1879
1427 608
608 1723
1723 1288
1288 779
7...

output:

1383 1215 618 642 652 620 644 654 624 646 657 628 647 669 637 1811 570 655 677 641 659 680 653 664 688 656 665 702 658 666 704 663 668 706 671 673 718 676 679 719 499 1048 1045 681 694 723 682 698 726 683 709 727 685 713 730 687 722 734 689 724 736 692 729 741 695 733 746 696 740 759 699 742 765 703...

result:

ok Accepted.

Test #56:

score: 18

Accepted

time: 6ms

memory: 40748kb

input:

1
1998 29319 1
93 1888
1888 701
701 643
643 1166
294 975
975 574
574 19
19 1224
1435 1480
72 1942
1707 613
613 1451
1272 769
1683 1050
1372 1242
1242 901
191 230
1702 562
562 883
1086 1964
1964 1852
1852 1955
1955 310
1165 1905
54 557
557 1182
1182 973
973 878
878 1950
1950 551
551 1473
1473 1921
11...

output:

430 151 715 662 717 577 722 579 745 580 746 584 749 595 763 596 765 601 713 605 785 618 787 620 789 623 799 636 811 640 818 641 821 644 822 649 824 655 827 656 767 572 609 478 622 482 626 484 629 490 638 505 650 1555 1097 506 665 509 670 514 674 1872 1018 1477 1753 857 1344 101 755 516 71 843 452 11...

result:

ok Accepted.

Test #57:

score: 18

Accepted

time: 3ms

memory: 40684kb

input:

1
1916 61288 2
395 1027
1610 1787
1787 357
189 139
139 675
675 1158
1158 1868
1868 1196
719 1579
1131 810
810 227
227 475
475 1060
1092 1602
1298 760
1390 211
211 1839
1839 99
99 618
618 1754
1754 1682
1682 529
529 1460
1555 1589
1589 152
152 1665
1665 1781
1649 1487
1487 870
870 144
144 934
750 162...

output:

1272 1527 631 663 629 660 628 657 624 652 623 649 621 646 620 633 2 581 615 625 614 618 612 284 607 486 672 1124 487 1851 611 601 605 600 604 591 603 583 616 630 697 727 691 724 686 721 684 720 683 711 682 709 680 706 679 705 634 664 673 694 667 690 662 689 654 688 644 687 642 674 636 671 635 665 67...

result:

ok Accepted.

Test #58:

score: 18

Accepted

time: 4ms

memory: 40480kb

input:

1
1835 91921 1
792 896
527 544
544 1461
1461 1426
1426 399
1350 1246
1246 496
496 227
227 799
799 546
945 779
779 418
1712 108
944 949
949 279
552 73
1311 1756
749 815
815 838
838 802
802 242
242 149
1482 1459
568 180
180 506
506 1270
758 1417
1417 203
898 178
178 386
386 920
920 467
715 76
76 1111
...

output:

784 796 666 565 665 563 663 558 661 555 660 554 658 546 656 580 654 540 648 539 646 534 645 531 639 530 637 528 634 526 633 524 632 545 629 638 628 635 625 630 624 626 623 620 6 618 643 616 721 581 719 606 718 603 715 600 712 598 711 590 710 589 706 584 701 523 699 613 695 473 622 466 691 464 686 45...

result:

ok Accepted.

Test #59:

score: 18

Accepted

time: 0ms

memory: 41696kb

input:

output:

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

result:

ok Accepted.

Test #60:

score: 18

Accepted

time: 0ms

memory: 40136kb

input:

output:

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

result:

ok Accepted.

Test #61:

score: 18

Accepted

time: 9ms

memory: 40688kb

input:

output:

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

result:

ok Accepted.

Test #62:

score: 18

Accepted

time: 10ms

memory: 40308kb

input:

output:

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

result:

ok Accepted.

Test #63:

score: 18

Accepted

time: 3ms

memory: 41724kb

input:

output:

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

result:

ok Accepted.

Test #64:

score: 18

Accepted

time: 3ms

memory: 41252kb

input:

output:

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

result:

ok Accepted.

Test #65:

score: 18

Accepted

time: 0ms

memory: 41524kb

input:

output:

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

result:

ok Accepted.

Test #66:

score: 18

Accepted

time: 0ms

memory: 41776kb

input:

output:

349 89 70 238 331 80 90 87 97 91 312 325 221 246 103 93 106 95 110 98 119 104 120 113 178 114 126 1 129 151 146 220 227 124 289 115 327 171 311 117 34 293 153 76 72 144 272 236 321 12 14 261 324 86 170 35 185 267 29 200 183 125 225 264 142 365 122 211 355 334 149 157 150 158 152 160 159 164 268 83 3...

result:

ok Accepted.

Test #67:

score: 18

Accepted

time: 4ms

memory: 41232kb

input:

output:

174 85 99 88 108 89 110 336 90 111 101 112 102 113 104 114 109 115 116 118 119 123 136 69 128 56 229 139 129 83 131 154 7 156 133 158 137 160 138 161 140 169 141 175 144 370 27 342 1 176 146 177 147 178 148 180 106 151 182 153 183 163 187 164 149 132 5 8 6 24 9 26 13 28 14 34 15 36 16 39 18 40 20 43...

result:

ok Accepted.

Subtask #8:

score: 10

Accepted

Dependency #7:

100%

Accepted

Test #68:

score: 10

Accepted

time: 28ms

memory: 39608kb

input:

output:

result:

ok Accepted.

Test #69:

score: 10

Accepted

time: 31ms

memory: 43124kb

input:

20
4739 5853376 2
241 1557
2727 144
828 4540
4356 4276
2664 1248
3140 3044
2673 2465
4472 4588
4088 1582
1402 837
249 2576
4222 2011
4326 3478
618 1837
2221 2758
4294 4571
4420 99
783 4166
2904 2230
2043 3395
4697 394
1658 1677
2315 931
4132 173
2863 4183
1156 2961
3832 4207
4175 2577
3526 2571
3844...

output:

2520 3761 1550 1619 1548 1618 1547 1616 1543 1615 1541 1612 1537 1611 1552 1610 1534 1220 1532 1597 1531 1594 1530 1591 1528 1590 1526 1589 1524 1587 1523 1584 1535 1606 1588 1654 1586 1650 1582 1647 1581 1645 1579 1643 1578 1642 1576 1640 1553 1621 1572 1637 1569 1636 1566 1630 1565 1629 1563 1627 ...

result:

ok Accepted.

Test #70:

score: 10

Accepted

time: 32ms

memory: 46624kb

input:

10
9775 28387496 2
4111 1845
5328 8463
5658 5847
3140 4296
2304 2863
3059 9597
3416 4942
4155 8323
5427 420
4277 6009
6681 2156
2015 6300
3901 7434
3626 7491
34 8881
2933 1589
2493 3247
3049 2124
7966 8151
7298 5798
4005 1543
6558 7955
7205 7231
6962 8747
9115 2347
6678 2313
6313 5913
5718 2087
4601...

output:

8467 9562 3224 3297 3227 3299 3228 3301 3229 3303 3233 3304 3234 3305 3235 3307 3236 3309 4 3325 3239 3311 3240 3312 3243 3316 3245 3320 3246 3321 3247 3322 3248 3323 3249 3324 3237 3310 3180 3238 3182 3241 3183 3242 3187 3244 3191 3252 3193 3257 3194 3259 3195 3263 3198 3289 3222 3266 3202 3268 320...

result:

ok Accepted.

Test #71:

score: 10

Accepted

time: 39ms

memory: 49420kb

input:

5
18424 102019945 1
6009 5000
688 5707
7377 2483
17135 11887
11730 10212
8202 2298
10379 4241
11435 9713
12686 1606
7194 701
4130 17140
12866 7314
5553 17608
17154 14894
476 15049
8664 31
16244 10749
7130 14423
15077 15440
3494 14841
14846 5537
15852 16565
9158 1139
9750 14771
16068 5101
5313 2422
9...

output:

11725 10850 4611 6197 6113 6196 6112 6195 6111 6194 6110 6193 6108 6191 6106 6190 6105 6238 6115 6188 6103 6185 6095 6184 6093 6181 6092 6180 6089 6179 6088 6177 6087 6172 6084 6189 6104 6237 6141 6236 6138 6235 6137 6234 6135 6229 6133 6227 6132 6226 6131 6222 6130 6198 6116 6219 6128 6215 6125 621...

result:

ok Accepted.

Test #72:

score: 10

Accepted

time: 49ms

memory: 57696kb

input:

3
31442 1897522 2
227 18045
19811 21817
17841 21143
23712 9546
31355 10107
2019 12690
10655 15526
21289 27919
21190 18604
762 28189
31092 22046
941 7045
25679 6271
341 5776
16779 28120
396 3989
18232 11559
24181 31300
6960 8713
12363 9404
18439 27196
16813 9762
10651 332
3494 20107
13995 26937
2428 ...

output:

25551 23689 9382 10369 9410 10372 9422 10402 9426 10405 9429 10428 9431 10432 9501 10452 9512 10472 9532 10355 9537 10529 9548 10542 9571 10586 9599 10596 9673 10632 9710 10639 9756 10647 9791 10698 7326 10713 9389 10526 9018 9858 9041 9948 9066 10030 9077 10043 9143 10048 9149 10056 9190 10072 9223...

result:

ok Accepted.

Test #73:

score: 10

Accepted

time: 37ms

memory: 53840kb

input:

3
32308 277196163 1
28236 28059
13478 9068
28454 28849
16817 246
11618 9818
28123 4662
20902 9080
13907 9158
5441 10539
27228 25652
13268 4496
13075 15781
9747 15408
24294 13278
29091 28311
3433 30055
20111 22336
24462 24005
16412 2106
17953 18082
11530 16617
17947 4128
2459 26569
9247 18592
19713 1...

output:

16122 17937 10752 10877 10748 10876 10747 10874 10743 10873 10742 10872 10740 10870 10738 10869 10737 10866 10736 10864 10732 10863 10731 10860 10727 10859 10726 10857 11084 10192 10722 10852 10720 10849 10719 10848 10717 10846 10715 10841 10711 10840 10710 10839 10706 10837 10705 10836 10704 10835 ...

result:

ok Accepted.

Test #74:

score: 10

Accepted

time: 16ms

memory: 41380kb

input:

233
427 58203 1
279 292
169 156
224 109
215 332
268 84
335 383
381 6
166 228
261 252
47 241
118 197
136 140
31 80
329 149
241 351
387 61
400 208
60 219
187 199
116 365
420 186
288 98
427 55
391 305
192 40
88 339
278 308
87 322
221 185
415 360
285 295
422 140
10 218
359 92
15 286
286 33
102 396
246 1...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
42 201 148 143 147 141 146 140 144 138 139 137 134 136 133 135 131 132 130 129 128 127 1 125 124 123 120 122 119 121 118 112 117 111 116 109 115 106 114 104 113 101 110 99 108 2 107 142 126 192 194 191 193 190 188 189 185 187 183 186 182 184 180 181 178 179 176...

result:

ok Accepted.

Test #75:

score: 10

Accepted

time: 31ms

memory: 41272kb

input:

output:

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

result:

ok Accepted.

Test #76:

score: 10

Accepted

time: 31ms

memory: 41352kb

input:

output:

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

result:

ok Accepted.

Test #77:

score: 10

Accepted

time: 30ms

memory: 40148kb

input:

output:

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

result:

ok Accepted.

Test #78:

score: 10

Accepted

time: 29ms

memory: 40312kb

input:

output:

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

result:

ok Accepted.

Test #79:

score: 10

Accepted

time: 30ms

memory: 41584kb

input:

500
181 10132 2
63 62
111 83
175 78
89 149
163 95
54 2
165 55
55 119
162 58
131 86
4 8
41 71
15 47
130 20
10 42
35 141
146 166
14 135
181 176
42 7
68 128
51 116
16 64
160 171
38 21
90 25
168 20
100 50
177 132
65 138
43 147
25 164
115 127
27 22
58 21
7 150
44 144
12 141
124 173
102 109
29 153
32 112
...

output:

135 154 52 47 53 49 57 50 60 51 64 54 65 55 68 56 69 58 70 59 96 2 74 62 75 63 76 66 77 67 84 71 85 73 89 78 93 79 94 80 95 81 72 82 3 61 12 4 13 5 14 6 16 7 17 8 19 9 22 10 26 11 27 15 48 18 29 46 30 21 31 23 32 24 33 25 34 36 35 38 37 40 39 41 43 42 44 45 28 20 141 130 142 131 143 136 144 146 145 ...

result:

ok Accepted.

Test #80:

score: 10

Accepted

time: 27ms

memory: 42732kb

input:

200
471 12114 2
415 145
297 397
304 440
14 104
181 443
273 49
105 78
84 2
212 53
432 390
394 451
468 286
127 263
113 238
171 196
59 117
392 349
215 94
356 442
344 338
192 86
66 257
241 450
306 26
272 142
161 384
58 196
218 463
93 23
312 372
54 308
308 68
452 345
51 247
418 76
122 8
198 139
424 108
5...

output:

471 387 134 95 140 99 150 101 160 104 162 106 163 113 164 114 171 116 172 121 176 126 177 1 183 141 189 143 190 145 195 149 196 152 198 156 203 168 205 169 206 170 213 180 226 191 234 193 139 137 8 4 13 5 16 6 24 11 27 14 32 17 36 26 38 28 50 29 58 187 34 60 41 228 94 78 52 90 53 91 57 92 63 100 67 ...

result:

ok Accepted.

Test #81:

score: 10

Accepted

time: 32ms

memory: 43188kb

input:

100
975 217172 2
649 311
744 359
221 637
308 496
259 838
859 382
738 637
17 87
454 452
546 664
703 942
867 284
754 964
12 467
114 932
36 393
390 469
42 328
115 480
462 329
39 8
233 588
86 130
325 316
872 258
341 967
967 162
941 288
687 871
258 356
321 468
581 476
31 813
133 538
635 824
331 377
71 50...

output:

937 932 287 321 288 326 290 331 294 334 295 335 296 336 299 337 300 338 303 342 304 344 307 349 345 383 310 354 312 355 313 356 314 358 318 360 322 361 323 366 327 368 328 371 329 376 330 377 332 379 340 380 309 350 228 251 229 252 232 254 233 256 234 258 237 260 238 262 247 266 249 267 250 268 253 ...

result:

ok Accepted.

Test #82:

score: 10

Accepted

time: 30ms

memory: 45588kb

input:

50
1867 423383 1
1402 1596
1768 1660
84 1611
368 1781
53 1341
996 1046
806 1866
1460 742
1359 1004
1863 605
489 250
388 1318
135 845
392 346
1257 855
654 77
490 640
1808 1148
384 614
1495 275
1196 1236
827 75
75 1712
254 726
1436 1432
1344 1476
728 739
1016 523
523 1837
381 1623
1703 1397
59 1827
52...

output:

833 1600 635 625 630 623 629 621 626 615 611 612 608 609 603 606 601 605 3 484 593 600 584 599 583 598 580 592 576 591 569 590 561 589 559 588 597 604 708 678 706 677 688 676 687 669 686 667 680 664 679 663 673 662 637 638 671 656 670 654 665 651 660 649 650 647 648 645 646 641 644 639 640 657 672 5...

result:

ok Accepted.

Subtask #9:

score: 22

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Dependency #5:

100%

Accepted

Dependency #6:

100%

Accepted

Dependency #7:

100%

Accepted

Dependency #8:

100%

Accepted

Test #83:

score: 22

Accepted

time: 124ms

memory: 38152kb

input:

output:

result:

ok Accepted.

Test #84:

score: 22

Accepted

time: 169ms

memory: 55828kb

input:

100
4914 5868584 2
4855 1980
1713 1299
1733 640
3936 2505
1258 1919
2989 2100
1549 1808
3837 534
2254 2130
459 1376
3914 200
2187 692
3465 2689
4501 1594
4516 3783
4095 3045
22 2133
1256 1369
1073 1136
646 3990
4506 3499
2663 3812
3649 3512
3573 2111
2241 2707
1879 2677
4216 2691
2878 1285
4604 4816...

output:

4138 1286 1617 1695 1614 1694 1613 1688 1612 1686 1611 1683 1610 1682 1605 1678 1604 1739 1602 1671 1598 1667 1596 1666 1595 1664 1592 1661 1591 1658 1211 1655 1616 1652 1657 1675 1656 1738 1653 1737 1651 1736 1650 1733 1645 1730 1644 1728 1590 1727 1638 1697 1637 1717 1636 1714 1633 1708 1631 1707 ...

result:

ok Accepted.

Test #85:

score: 22

Accepted

time: 175ms

memory: 60192kb

input:

50
9264 14343522 2
4127 3748
8726 7859
1654 448
5251 8559
2277 3834
8033 4427
8913 6115
759 3415
671 312
1678 2639
6702 2797
3520 7485
464 1726
2509 6969
3491 6541
1904 4841
443 3242
6363 7280
2589 1882
2697 5015
9186 9026
125 70
2312 5699
5927 4834
4402 4396
7256 8408
2441 5044
1999 3156
564 3901
2...

output:

7377 2153 3089 3230 3084 3227 3081 3222 3080 3220 3078 3216 3075 3215 3073 3214 3072 3213 3071 3208 3067 3205 3065 3202 3091 3189 3061 3231 3060 3186 3059 3184 3058 3170 3057 3165 3052 3160 3048 3156 3045 3149 3033 3147 3032 3146 3030 3139 3028 3126 3026 3125 3062 3188 3151 3332 3150 3328 3148 3327 ...

result:

ok Accepted.

Test #86:

score: 22

Accepted

time: 171ms

memory: 59276kb

input:

50
9392 58225 1
6228 6729
316 3831
4383 827
4783 206
901 8057
8725 8920
6509 5267
2014 6918
7013 8718
699 1492
7298 8293
309 3846
5194 5883
3758 6754
7087 2643
2026 4947
7467 4209
5897 1024
7167 8508
4305 2042
6807 9031
2272 3612
7696 4195
3339 8474
8564 1256
8979 1773
3222 4076
4412 8107
27 3558
23...

output:

5717 5559 3442 2666 3430 2651 3374 2618 3359 2529 3319 2477 3108 2445 3096 2437 3074 2400 3056 2378 3021 3962 4783 2327 2982 2310 2925 2308 2816 2282 2798 2269 2725 2127 2597 2125 2581 2066 2550 2058 2515 2045 2493 2040 2300 2351 2986 3958 4751 3899 4657 3805 4639 3747 4615 3736 4569 3732 4491 3724 ...

result:

ok Accepted.

Test #87:

score: 22

Accepted

time: 190ms

memory: 61580kb

input:

25
19790 20927306 2
4444 6276
14933 10108
6231 5388
15299 4203
17068 12794
10252 8287
6787 4058
2947 7053
16913 8475
5104 4109
10834 9443
11748 12927
8388 16660
4325 9605
16413 2446
16668 323
2038 4364
19597 2386
17857 2971
12045 2107
10345 15034
5324 4685
1910 9248
19068 3915
8777 3401
17337 2365
1...

output:

12777 10911 6645 6730 6637 6725 6636 6717 6630 6711 6624 6707 6618 6704 6617 6696 6613 6692 6604 6690 6594 6689 6591 6684 6590 6671 6586 6666 6585 6664 6649 6663 6579 7490 6577 6646 6570 6644 6569 6643 6567 6642 6562 6640 6559 6639 6546 6626 6544 6619 6542 6614 6532 6610 6528 6609 6517 6595 6515 658...

result:

ok Accepted.

Test #88:

score: 22

Accepted

time: 182ms

memory: 59212kb

input:

25
19975 93145930 2
12432 1834
1881 14484
15930 10534
10845 7335
8074 9798
361 16500
1801 6929
4437 3207
14447 5118
6677 4193
1052 4088
869 640
15256 8605
8186 18363
15464 3806
5778 17272
9822 14677
5350 15754
1674 18160
1783 8216
15853 14470
14582 12437
2545 812
1606 18202
19624 9375
1895 6171
8629...

output:

6648 13968 6675 6670 6707 6667 6703 6666 6702 6665 6701 6664 6698 6663 6692 6672 6691 6660 6690 6654 6685 6653 6683 6652 6682 6651 6680 6647 6679 6646 6677 6645 6709 6662 6750 6708 6745 6706 6744 6705 6740 6704 6736 6699 6735 6697 6733 6696 6711 6673 6731 6687 6729 6686 6728 6684 6727 6681 6719 6678...

result:

ok Accepted.

Test #89:

score: 22

Accepted

time: 216ms

memory: 71572kb

input:

10
47976 591885312 2
5124 43680
2252 9516
19288 8740
28470 38971
44005 16449
35113 31009
7142 23054
26551 47176
10450 26089
21857 23087
41980 36670
42848 35489
10282 16403
5395 30470
15802 45845
17969 7447
34743 7617
34799 20623
34264 26807
33968 43764
29498 27833
40072 29805
28680 33112
22228 26794...

output:

47561 30821 15893 16127 15898 16129 15899 16130 15905 16131 15907 16132 15909 16134 15914 16137 15915 16138 15916 16139 15937 16126 15921 16143 15922 16144 15923 16145 15924 16146 15928 16147 15930 16149 15932 16150 15933 16151 15934 16152 15936 16153 15918 16142 15836 16081 15838 16084 15840 16085 ...

result:

ok Accepted.

Test #90:

score: 22

Accepted

time: 213ms

memory: 76928kb

input:

10
45442 215847028 1
18473 30982
44534 41274
2723 45201
13119 6426
38639 43918
31640 2906
32096 15308
1356 8922
22081 4880
45055 5993
13173 20550
16941 19759
16629 2018
19954 43873
13002 18173
11394 28098
41851 25383
5142 31705
27108 15842
35992 22440
32300 24908
6264 14876
8386 39768
27107 20226
11...

output:

4860 15065 15097 15064 15095 15063 15090 15055 15086 15054 15084 15050 15080 15045 15074 15040 15071 15039 15061 15038 15060 15032 15059 15028 15053 15066 17029 15025 15051 15020 15048 15019 15046 15017 15044 15012 15043 15007 15042 15005 15036 15004 15029 15001 15023 15000 15022 14998 15021 15026 1...

result:

ok Accepted.

Test #91:

score: 22

Accepted

time: 230ms

memory: 97000kb

input:

5
98026 412627902 2
48046 18927
13901 28466
35521 5201
80007 11667
80793 96581
55539 20025
5543 85851
55543 21411
29340 34851
29610 60263
18792 84130
32073 75581
78498 30643
1376 11678
50702 79538
3515 33613
58947 90914
32141 54510
97107 57425
16944 15325
26833 50683
53820 39405
4095 9382
40911 6943...

output:

66903 54951 32719 32978 32722 32984 32728 32987 32745 32988 32747 32989 32751 32994 32756 33007 32757 33258 32813 33009 32770 33019 32771 33025 32775 33026 32784 33028 32794 33038 32803 33044 32804 33046 32768 33008 32620 32881 32624 32890 32631 32895 32638 32900 32645 32902 32649 32904 32651 32910 ...

result:

ok Accepted.

Test #92:

score: 22

Accepted

time: 258ms

memory: 93872kb

input:

5
91305 1628174951 1
56198 20850
52916 85909
35476 56437
1834 9115
12192 10250
42982 57176
9593 27306
24150 48020
65107 42644
78643 42705
52340 56849
10078 23282
57269 5876
77632 26605
32767 24018
81204 21219
47096 12948
33055 2485
54922 15109
4406 72601
71077 36886
57706 24314
9215 42336
36145 6145...

output:

45523 22901 29819 30752 29818 30745 29813 30744 29812 30743 29807 30740 29804 30737 29798 30735 29716 30731 29794 30630 29793 30728 29790 30727 29786 30724 29784 30723 29783 30721 29780 30717 29779 30716 29795 30729 29855 30812 29852 30810 29851 30808 29850 30796 29849 30794 29848 30790 29846 30787 ...

result:

ok Accepted.

Test #93:

score: 22

Accepted

time: 376ms

memory: 215016kb

input:

1
472025 16043466085 1
417926 39623
195768 229314
370537 57531
267104 382113
170933 141578
53561 74294
250159 31886
9352 36181
322148 394068
117039 351210
300887 304015
24549 24940
114489 128610
411952 339863
71691 11387
73530 4523
10760 14371
149252 155462
22680 357719
350109 402379
152082 101050
2...

output:

250496 323822 158527 157397 158534 157402 158540 157407 158546 157410 158550 157422 158552 157423 158558 157425 158567 157430 158568 157433 158569 157434 158572 157435 158575 157439 158866 157394 158585 157450 158587 157452 158590 157453 158595 157458 158600 157462 158606 157463 158607 157475 158614...

result:

ok Accepted.

Test #94:

score: 22

Accepted

time: 165ms

memory: 41436kb

input:

output:

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

result:

ok Accepted.

Test #95:

score: 22

Accepted

time: 362ms

memory: 225744kb

input:

1
482724 69862381824 1
137472 24627
53394 136713
29923 24872
183115 104962
360179 53778
95044 16923
208793 216766
343809 82383
389111 122728
267129 163660
381943 86337
191746 130719
179638 171500
16541 49248
9266 60892
245541 12470
324537 105560
368925 467572
480713 67654
10418 410596
140876 300727
...

output:

4466 160694 161129 160692 161127 160691 161126 160690 161119 160689 161118 160686 161116 160683 161113 160682 161112 160677 161110 160675 161107 160674 161106 160671 161104 160670 161102 160637 161101 160656 161195 160655 161097 160653 161096 160651 161094 160650 161091 160649 161090 160648 161089 1...

result:

ok Accepted.

Test #96:

score: 22

Accepted

time: 351ms

memory: 219020kb

input:

1
466556 37068012357 1
296077 254374
55895 139417
250053 262476
281210 151748
361746 75307
38308 211
25635 226913
290473 170308
112117 207274
333222 333380
165721 128597
76733 301893
137129 112197
171945 20656
193257 43287
93646 249912
343755 80957
434796 359970
277965 34924
188290 4117
401431 43469...

output:

312653 416033 155588 155651 155582 155650 155578 155649 155570 155648 155565 155645 155564 155644 155563 155642 155560 155641 155522 155613 155550 155635 155549 155634 155548 155633 155545 155626 155543 155624 155538 155623 155534 155622 155529 155617 155528 155616 155523 155615 155559 155637 155652...

result:

ok Accepted.

Test #97:

score: 22

Accepted

time: 372ms

memory: 213472kb

input:

1
470507 15553613111 1
116590 375013
25458 460568
274726 423221
185476 26173
129323 115569
393959 379177
186613 320883
413505 47092
298840 72519
445171 170296
28563 18974
198881 343336
153370 1813
428633 372899
188361 262767
97460 411511
23648 449045
388428 367955
10793 398742
305885 3039
441903 422...

output:

353265 397678 156405 157418 156409 157598 156410 157607 156413 157612 156418 157613 156422 157619 156427 157621 156440 157623 156444 157628 156445 157639 156447 157650 156449 157656 156399 157659 156455 157660 156460 157661 156464 157663 156477 157674 156483 157676 156485 157678 156486 157684 156491...

result:

ok Accepted.

Test #98:

score: 22

Accepted

time: 366ms

memory: 227812kb

input:

1
484644 70415722676 2
387061 60091
283751 60069
107460 354884
445876 55307
338664 281406
388782 24215
35572 117625
177669 98530
7682 233035
116725 414416
355609 95819
475062 198221
241991 472832
44124 13983
140233 377622
213795 216775
272564 443204
119914 351907
326597 142211
466195 381175
457028 2...

output:

271472 222774 161872 161221 161869 161218 161867 161215 161866 161214 161865 161207 161863 161206 161862 161205 161861 161204 161859 161203 161858 161202 161857 161201 161855 161200 161854 161199 161937 161162 161849 161195 161848 161194 161846 161192 161844 161191 161842 161189 161839 161188 161835...

result:

ok Accepted.

Test #99:

score: 22

Accepted

time: 331ms

memory: 226604kb

input:

1
480049 66333578702 2
414780 52384
229954 204017
477598 350060
177290 395393
22600 399649
194443 4952
375752 445636
81605 302911
366288 84718
57315 335522
472784 367329
137447 408097
409021 236863
121965 347700
346918 58159
445793 183641
255068 367810
442172 237707
471652 352900
286081 25476
89138 ...

output:

76397 386045 159917 160115 159916 160114 159913 160112 159912 160109 159908 160105 159905 160102 159904 160100 159902 160098 159898 160096 159896 160095 159894 160091 159892 160090 159890 160048 1 160083 159887 160079 159884 160077 159881 160076 159875 160075 159874 160071 159873 160069 159872 16006...

result:

ok Accepted.

Test #100:

score: 22

Accepted

time: 77ms

memory: 42612kb

input:

1000
498 181292 1
55 405
423 313
133 192
359 39
367 203
366 42
100 76
358 263
183 445
87 27
114 402
331 371
272 424
394 194
417 268
285 284
328 59
125 495
495 364
201 407
310 18
337 283
213 154
346 229
16 65
341 480
315 252
393 19
7 153
365 86
95 144
287 349
262 470
332 295
424 255
336 491
491 311
6...

output:

-1
424 172 184 171 183 170 178 168 169 164 167 159 166 158 165 156 163 155 162 150 161 148 160 147 157 146 258 173 153 142 152 140 151 139 216 149 138 145 137 144 134 141 131 136 130 135 128 133 126 132 125 129 124 127 121 123 143 154 224 256 222 252 220 250 219 247 218 246 217 245 213 242 209 239 2...

result:

ok Accepted.

Test #101:

score: 22

Accepted

time: 157ms

memory: 41284kb

input:

output:

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

result:

ok Accepted.

Test #102:

score: 22

Accepted

time: 155ms

memory: 41568kb

input:

2000
230 11927 1
198 69
181 202
214 145
16 114
211 199
20 92
100 194
177 145
55 228
228 152
101 138
203 42
137 186
36 77
189 152
152 196
6 22
57 123
123 213
213 27
217 157
187 127
22 172
172 168
224 155
33 144
144 13
167 166
61 209
135 175
48 200
199 124
50 230
161 109
190 226
30 155
86 79
79 183
29...

output:

184 26 70 56 74 58 75 60 79 61 83 66 85 67 86 71 87 73 89 77 91 78 123 81 96 1 98 84 100 90 101 92 103 94 104 95 105 97 108 102 109 106 111 107 112 192 115 114 116 93 82 4 6 11 7 13 8 16 9 17 10 19 14 21 18 25 20 27 22 28 29 33 30 69 55 38 34 40 36 47 39 48 42 50 43 57 44 59 45 62 49 63 51 64 52 65 ...

result:

ok Accepted.

Test #103:

score: 22

Accepted

time: 163ms

memory: 43676kb

input:

output:

94 201 51 114 100 54 105 127 409 435 333 140 138 361 157 218 296 215 53 109 150 395 76 338 422 14 170 52 449 343 192 112 240 89 128 236 424 74 28 407 158 211 363 301 135 96 205 271 60 252 312 82 46 341 169 147 417 117 286 59 442 175 303 268 418 151 102 280 245 384 359 97 427 310 159 193 191 380 244 ...

result:

ok Accepted.

Test #104:

score: 22

Accepted

time: 155ms

memory: 47996kb

input:

output:

971 465 630 463 490 422 408 421 375 415 373 683 826 505 633 712 270 131 153 340 961 715 129 770 204 190 410 241 732 450 697 226 718 18 57 144 562 203 58 517 865 569 108 279 969 821 158 162 662 716 352 603 345 778 446 406 33 687 571 860 407 934 591 859 194 566 180 97 320 805 856 3 83 698 335 883 926 ...

result:

ok Accepted.

Test #105:

score: 22

Accepted

time: 144ms

memory: 46276kb

input:

500
962 55094 2
235 718
135 459
342 659
434 460
921 812
495 217
751 340
546 326
439 820
337 780
523 223
658 277
938 947
701 493
809 501
198 895
883 554
293 504
627 939
103 688
297 215
26 828
3 402
273 885
190 172
470 871
465 889
244 698
356 926
878 940
23 961
730 476
906 459
80 479
823 139
881 395
3...

output:

571 511 332 367 329 359 322 351 318 350 313 349 310 348 309 346 294 341 286 335 281 334 336 333 273 378 272 325 269 321 268 297 261 898 293 259 292 258 290 257 288 247 285 245 283 244 282 238 279 277 331 489 512 485 506 480 504 474 502 470 493 455 491 454 490 447 481 439 479 438 472 432 469 344 382 ...

result:

ok Accepted.

Test #106:

score: 22

Accepted

time: 165ms

memory: 54916kb

input:

100
4746 1051132 2
1237 3867
2107 4075
3048 3224
2208 1419
3875 1498
598 1118
4554 3504
1732 1316
1594 1279
3626 2781
2662 3766
3719 4529
4566 3799
178 2964
340 768
2823 3777
217 2269
2504 2945
345 4068
2882 3668
2116 471
2368 3872
606 1614
2884 961
1854 4389
4510 920
3424 2284
3637 2875
1692 2741
1...

output:

339 1322 1508 1635 1503 1631 1499 1629 1485 1624 1484 1620 1483 1608 1479 1607 1469 1598 1466 1596 1462 1595 1461 1591 1455 1587 1452 1636 1106 1580 1449 1579 1447 1574 1446 1571 1436 1568 1426 1563 1408 1561 1404 1560 1400 1544 1399 1531 1387 1530 1378 1528 1377 1522 1372 1515 1451 1581 1625 1806 1...

result:

ok Accepted.

Test #107:

score: 22

Accepted

time: 153ms

memory: 55876kb

input:

100
4503 2286264 1
1641 2688
3396 2617
2562 833
1305 2310
638 850
2450 2086
1235 1661
4143 1757
3412 3937
1584 12
1159 736
3175 3109
1202 2747
3778 3893
1592 1029
203 982
3709 1326
2540 2325
2707 893
43 2008
2203 2422
1901 3772
559 3365
4355 2942
1770 3316
2864 2218
2544 359
763 4500
3537 2236
376 2...

output:

666 1492 1416 1494 1417 1500 1418 1505 1421 1506 1426 1509 1427 1513 1428 1516 1429 1517 1432 2225 1438 1519 1441 1520 1444 1522 1446 1523 1448 1527 1455 1528 1457 1529 1458 1531 1460 1532 1461 1549 1437 1518 1088 1405 1361 1411 1362 1413 1365 1419 1367 1420 1368 1440 1373 1442 1376 1443 1380 1447 1...

result:

ok Accepted.