QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#69460#5307. Subgraph Isomorphismmagicduck#WA 1408ms10008kbC++142.9kb2022-12-27 17:31:062023-10-15 17:23:43

Judging History

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

  • [2023-10-15 17:23:43]
  • 管理员手动重测本题所有提交记录
  • 测评结果:WA
  • 用时:1408ms
  • 内存:10008kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-27 17:31:07]
  • 评测
  • 测评结果:0
  • 用时:1994ms
  • 内存:9892kb
  • [2022-12-27 17:31:06]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
template <typename T> inline void read(T &F) {
    int R = 1; F = 0; char CH = getchar();
    for(; !isdigit(CH); CH = getchar()) if(CH == '-') R = -1;
    for(; isdigit(CH); CH = getchar()) F = F * 10 + CH - 48;
    F *= R;
}
inline void file(string str) {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
}
const int N = 1e5 + 10;
int fa[N], now, fst[N], nxt[N << 1], num[N << 1], siz[N], g[N], R, n, m;
void add(int u, int v) {
    nxt[++now] = fst[u], fst[u] = now, num[now] = v;
    nxt[++now] = fst[v], fst[v] = now, num[now] = u;
}
unsigned long long f[N];
const unsigned long long A = 1e9 + 9, B = 19260817, C = 97;
unsigned long long h(unsigned long long x) {
    return A * x * x * x + B * x + C;
}
unsigned long long suan(unsigned long long x) {
    return h(x & ((1ull << 32) - 1)) + h(x >> 32);
}
void dfs(int x, int y) {
    f[x] = 137137;
    for(int i = fst[x]; i; i = nxt[i]) {
        const int z = num[i];
        if(z == y) continue; dfs(z, x);
        f[x] += suan(f[z]);
    }
}
void calc(int x) {
    siz[x] = 1; g[x] = 0;
    for(int i = fst[x]; i; i = nxt[i]) {
        if(num[i] == fa[x]) continue;
        fa[num[i]] = x;
        calc(num[i]); siz[x] += siz[num[i]];
        g[x] = max(g[x], siz[num[i]]);
    }
    g[x] = max(g[x], n - siz[x]);
    if(g[x] < g[R]) R = x;
} 
int get_fa(int x) {
    return fa[x] == x ? x : fa[x] = get_fa(fa[x]);
}
pair<int, int> edge[N]; 
unsigned long long ran() {
    random_shuffle(edge + 1, edge + m + 1);
    for(int i = 1; i <= n + 1; i++) fst[i] = 0, fa[i] = i; now = 0;
    vector<pair<int, int> > e;
    for(int i = 1; i <= m; i++) {
        const int x = edge[i].first, y = edge[i].second;
        if(get_fa(x) == get_fa(y)) continue;
        e.emplace_back(x, y); add(x, y);
        fa[get_fa(x)] = get_fa(y);
    }
    fa[1] = R = 0; g[R] = 1e9;
    calc(1); int a = 0, b = 0, c = n, r = 0;
    if(g[R] == g[fa[R]]) c = n + 1, a = R, b = fa[R], e.emplace_back(n + 1, a), e.emplace_back(n + 1, b), r = n + 1; else a = R, r = R;
    now = 0;
    for(int i = 1; i <= n + 1; i++) fst[i] = 0;
    for(auto i : e) {
        if((i.first == a && i.second == b) || (i.first == b && i.second == a)) continue;
        add(i.first, i.second);
    } 
    dfs(r, 0); return f[r] * A + c;
}
int main() {
    //file("test");
    srand(time(0));
    int T; read(T);
    while(T--) {
        read(n), read(m);
        for(int i = 1; i <= m; i++) read(edge[i].first), read(edge[i].second);
        unsigned long long G = ran(); int flag = 1;
        for(int i = 1; i <= 25; i++)
            if(ran() != G) {
                puts("NO"); flag = 0; break;
            }
        if(flag) puts("YES");
    }
    #ifdef _MagicDuck
        fprintf(stderr, "# Time: %.3lf s", (double)clock() / CLOCKS_PER_SEC);
    #endif
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 5956kb

input:

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

output:

YES
YES
NO
YES

result:

ok 4 token(s): yes count is 3, no count is 1

Test #2:

score: 0
Accepted
time: 57ms
memory: 5608kb

input:

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

output:

YES
YES
YES
YES
YES
NO
YES
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
YES
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO...

result:

ok 33192 token(s): yes count is 58, no count is 33134

Test #3:

score: 0
Accepted
time: 72ms
memory: 5720kb

input:

40000
9 24
1 4
1 6
1 7
1 9
2 5
2 7
2 8
2 9
3 5
3 7
3 8
3 9
4 6
4 8
4 9
5 6
5 8
5 9
6 7
6 8
6 9
7 8
7 9
8 9
9 21
1 4
1 6
1 7
1 8
2 5
2 7
2 8
2 9
3 5
3 7
3 9
4 6
4 8
4 9
5 6
5 9
6 7
6 8
6 9
7 8
8 9
9 21
1 4
1 6
1 7
1 8
2 5
2 7
2 8
2 9
3 5
3 7
3 9
4 6
4 8
4 9
5 6
5 9
6 7
6 8
6 9
7 8
7 9
9 22
1 4
1 6
1 ...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 40000 token(s): yes count is 0, no count is 40000

Test #4:

score: 0
Accepted
time: 68ms
memory: 5712kb

input:

40000
9 16
1 4
1 6
1 8
1 9
2 5
2 7
2 8
2 9
3 6
3 7
4 7
5 8
6 9
7 8
7 9
8 9
9 16
1 4
1 6
1 8
1 9
2 5
2 7
2 8
2 9
3 6
3 7
4 7
5 8
5 9
7 8
7 9
8 9
9 16
1 4
1 6
1 8
1 9
2 5
2 7
2 8
2 9
3 6
3 7
4 7
5 8
5 9
6 9
7 8
8 9
9 16
1 4
1 6
1 8
1 9
2 5
2 7
2 8
2 9
3 6
3 7
4 7
5 8
5 9
6 9
7 8
7 9
9 17
1 4
1 6
1 8
1...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 40000 token(s): yes count is 0, no count is 40000

Test #5:

score: 0
Accepted
time: 71ms
memory: 5656kb

input:

40000
9 17
1 5
1 6
1 7
1 8
2 5
2 7
2 9
3 6
3 8
3 9
4 7
4 8
4 9
5 7
5 8
5 9
6 9
9 18
1 5
1 6
1 7
1 8
2 5
2 7
2 9
3 6
3 8
3 9
4 7
4 8
4 9
5 7
5 8
5 9
6 9
8 9
9 18
1 5
1 6
1 7
1 8
2 5
2 7
2 9
3 6
3 8
3 9
4 7
4 8
4 9
5 7
5 8
5 9
6 9
7 9
9 19
1 5
1 6
1 7
1 8
2 5
2 7
2 9
3 6
3 8
3 9
4 7
4 8
4 9
5 7
5 8
5 ...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 40000 token(s): yes count is 0, no count is 40000

Test #6:

score: 0
Accepted
time: 69ms
memory: 5720kb

input:

40000
9 17
1 5
1 6
1 7
1 8
2 6
2 7
2 8
2 9
3 7
3 9
4 9
5 8
6 7
6 8
6 9
7 9
8 9
9 16
1 5
1 6
1 7
1 8
2 6
2 7
2 8
2 9
3 7
3 9
4 9
5 8
5 9
6 7
6 8
8 9
9 16
1 5
1 6
1 7
1 8
2 6
2 7
2 8
2 9
3 7
3 9
4 9
5 8
5 9
6 7
6 8
7 9
9 17
1 5
1 6
1 7
1 8
2 6
2 7
2 8
2 9
3 7
3 9
4 9
5 8
5 9
6 7
6 8
7 9
8 9
9 17
1 5
1...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 40000 token(s): yes count is 0, no count is 40000

Test #7:

score: 0
Accepted
time: 67ms
memory: 7768kb

input:

40000
9 15
1 5
1 8
1 9
2 6
2 7
2 9
3 6
3 7
4 7
4 8
4 9
5 8
6 9
7 9
8 9
9 13
1 5
1 8
1 9
2 6
2 7
2 9
3 6
3 7
4 7
4 8
4 9
5 8
5 9
9 14
1 5
1 8
1 9
2 6
2 7
2 9
3 6
3 7
4 7
4 8
4 9
5 8
5 9
8 9
9 14
1 5
1 8
1 9
2 6
2 7
2 9
3 6
3 7
4 7
4 8
4 9
5 8
5 9
7 9
9 15
1 5
1 8
1 9
2 6
2 7
2 9
3 6
3 7
4 7
4 8
4 9
5...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 40000 token(s): yes count is 1, no count is 39999

Test #8:

score: 0
Accepted
time: 65ms
memory: 5792kb

input:

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

output:

YES
YES
NO
YES
YES
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
N...

result:

ok 40000 token(s): yes count is 50, no count is 39950

Test #9:

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

input:

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

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 1393 token(s): yes count is 0, no count is 1393

Test #10:

score: 0
Accepted
time: 40ms
memory: 7760kb

input:

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

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 3000 token(s): yes count is 0, no count is 3000

Test #11:

score: 0
Accepted
time: 708ms
memory: 9828kb

input:

30
28171 28170
2482 5158
15414 17513
7825 17196
10171 8545
8850 13596
3314 9296
5490 15625
18905 9569
24135 6453
360 718
65 27875
13734 20008
20072 4447
23395 24852
11440 1818
20672 13049
13770 6079
19115 24044
22134 24300
15787 3053
6462 6652
3200 14184
20621 629
1328 5200
7181 17707
4515 18911
249...

output:

YES
NO
NO
NO
YES
YES
NO
NO
NO
NO
YES
NO
NO
NO
YES
YES
YES
NO
YES
NO
NO
NO
NO
NO
YES
YES
NO
NO
YES
YES

result:

ok 30 token(s): yes count is 12, no count is 18

Test #12:

score: 0
Accepted
time: 850ms
memory: 9740kb

input:

30
3658 3658
1673 1805
115 1360
145 1722
3398 2869
700 3578
2145 60
3563 2682
2957 307
2443 1048
3581 2555
2368 2336
1023 3041
664 412
1950 552
3425 1162
3159 3296
1373 1763
1336 3591
1119 1992
1912 354
3573 3124
1351 1022
3047 2879
2521 1939
1683 1679
1070 1259
1342 1637
732 2576
2167 3067
2742 514...

output:

NO
NO
YES
YES
NO
YES
YES
NO
NO
NO
YES
NO
NO
NO
YES
NO
YES
YES
NO
YES
NO
YES
NO
YES
NO
YES
YES
NO
NO
NO

result:

ok 30 token(s): yes count is 13, no count is 17

Test #13:

score: 0
Accepted
time: 1408ms
memory: 9872kb

input:

30
6200 6199
2543 3295
1003 4780
4627 4563
5620 660
1731 3047
1198 3343
3419 4710
2488 3843
3722 4576
752 3212
5313 4025
4612 286
1967 1397
36 2212
1206 928
4689 1268
2831 4376
4334 3028
1040 1514
5636 5331
4257 571
5182 5007
1629 208
2345 3406
5280 4999
2607 2254
6192 1403
5075 3889
3389 5294
3682 ...

output:

YES
NO
YES
YES
YES
NO
YES
NO
NO
NO
YES
NO
NO
YES
NO
YES
NO
NO
YES
YES
YES
NO
NO
YES
YES
YES
NO
YES
NO
YES

result:

ok 30 token(s): yes count is 16, no count is 14

Test #14:

score: 0
Accepted
time: 1334ms
memory: 10008kb

input:

30
14491 14490
6052 10994
13301 461
1336 9631
10722 4121
9829 5812
11883 5039
4854 6739
4064 11033
466 6698
2959 4374
3041 3663
5616 3289
458 788
4018 8915
13689 2763
14153 14146
2336 9011
7827 11114
9235 13235
4091 5135
8099 10920
4359 13623
10194 870
3222 11124
13620 2624
4477 7638
12926 10795
506...

output:

YES
YES
NO
NO
YES
NO
NO
NO
YES
NO
YES
NO
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
NO

result:

ok 30 token(s): yes count is 18, no count is 12

Test #15:

score: 0
Accepted
time: 703ms
memory: 9696kb

input:

30
100000 99999
58634 53166
60069 39545
82578 88227
56874 85747
22905 28646
92672 64752
22373 59305
22541 59348
44095 65942
4988 67515
10343 77755
60473 69842
23600 65125
30620 9705
23682 88606
90443 30376
64660 28469
49987 74473
95538 6848
57849 92719
41776 11339
34932 41927
53269 36288
27451 77680...

output:

YES
NO
YES
NO
YES
NO
YES
NO
YES
NO
NO
YES
NO
NO
YES
YES
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
YES
YES

result:

ok 30 token(s): yes count is 12, no count is 18

Test #16:

score: 0
Accepted
time: 618ms
memory: 9828kb

input:

30
28822 28821
18849 2213
3904 10406
22000 14733
3382 11686
18120 2209
16720 21313
27796 11273
2151 1627
14221 1730
28679 13010
13611 8540
8923 13036
14093 25113
28268 1341
22450 5687
24407 28379
28185 19130
9949 4590
19825 24477
24266 21368
15658 20039
19834 22900
10711 27768
21931 21505
701 5260
2...

output:

YES
NO
YES
YES
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
YES
NO
NO
YES
YES
YES
NO
NO
YES
NO
NO
YES
YES
NO
NO
YES

result:

ok 30 token(s): yes count is 14, no count is 16

Test #17:

score: 0
Accepted
time: 800ms
memory: 9820kb

input:

30
94155 94155
59782 9369
85417 55440
49151 38561
70569 2997
58372 92455
55440 13968
23987 25454
31693 59782
28401 47143
70435 87698
29557 80207
71824 24642
52316 53847
52316 49058
26005 29924
42139 19301
57171 76189
41506 59782
41871 88927
2997 10080
41910 83200
52724 3425
55302 18910
72572 45110
6...

output:

NO
YES
NO
YES
YES
NO
YES
NO
NO
YES
YES
NO
YES
NO
YES
NO
YES
YES
NO
YES
YES
YES
NO
NO
YES
NO
NO
NO
NO
NO

result:

ok 30 token(s): yes count is 14, no count is 16

Test #18:

score: 0
Accepted
time: 946ms
memory: 5716kb

input:

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

output:

NO
YES
YES
YES
YES
YES
NO
YES
YES
NO
NO
YES
YES
NO
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
NO
YES
YES
YES
NO
YES
YES
YES
NO
NO
YES
YES
NO
YES
NO
NO
YES
NO
YES
NO
YES
NO
NO
YES
YES
YES
YES
YES
YES
...

result:

ok 100000 token(s): yes count is 62089, no count is 37911

Test #19:

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

input:

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

output:

YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
NO
YES
YES
NO
NO
YES
YES
NO
YES
NO
YES
YES
NO
NO
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
NO
NO
YES
NO
YES
YES
YES
YES
NO
NO
NO
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
NO
NO
YES
...

result:

ok 100000 token(s): yes count is 63111, no count is 36889

Test #20:

score: 0
Accepted
time: 918ms
memory: 5956kb

input:

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

output:

NO
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
NO
YES
NO
NO
YES
NO
YES
NO
YES
NO
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
NO
NO
NO
NO
NO
YES
NO
YES
NO
YES
NO
NO
YES
YES
YES
YES
NO
NO
NO
YES
NO
YES
YES
YES
NO
NO
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES...

result:

ok 100000 token(s): yes count is 63673, no count is 36327

Test #21:

score: 0
Accepted
time: 936ms
memory: 7760kb

input:

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

output:

YES
YES
YES
YES
YES
YES
NO
YES
YES
NO
NO
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
YES
YES
YES
YES
YES
YES
NO
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
NO
NO
NO
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
NO
YES
YE...

result:

ok 100000 token(s): yes count is 63794, no count is 36206

Test #22:

score: 0
Accepted
time: 791ms
memory: 5888kb

input:

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

output:

YES
YES
YES
YES
NO
YES
NO
YES
NO
YES
YES
NO
YES
YES
NO
NO
YES
YES
NO
NO
YES
NO
NO
NO
YES
YES
YES
YES
YES
NO
YES
NO
NO
NO
NO
YES
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
NO
NO
YES
YES
NO
NO
YES
NO
YES
NO
NO
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
...

result:

ok 100000 token(s): yes count is 60664, no count is 39336

Test #23:

score: -100
Wrong Answer
time: 679ms
memory: 5788kb

input:

100000
22 22
18 20
18 6
18 11
18 12
11 5
19 18
5 18
9 18
18 1
15 18
17 18
18 22
16 18
18 4
10 18
7 18
13 18
2 18
18 21
8 18
3 18
14 18
14 13
6 13
6 10
6 11
6 5
4 6
7 6
3 6
6 2
12 6
6 9
8 6
14 6
1 6
49 48
29 1
29 45
29 42
29 11
24 29
27 29
29 2
29 17
29 10
29 41
26 29
29 3
29 28
29 35
14 24
29 43
34 ...

output:

NO
YES
YES
YES
YES
NO
YES
YES
NO
YES
NO
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
NO
YES
NO
YES
NO
NO
NO
NO
YES
YES
NO
NO
NO
YES
YES
YES
YES
NO
YES
YES
NO
NO
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
Y...

result:

wrong answer expected NO, found YES [16788th token]