QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#319115#1195. One-Way ConveyorschmproTL 24ms7960kbC++204.3kb2024-02-01 21:49:352024-02-01 21:49:35

Judging History

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

  • [2024-02-01 21:49:35]
  • 评测
  • 测评结果:TL
  • 用时:24ms
  • 内存:7960kb
  • [2024-02-01 21:49:35]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define vi  vector<int>
#define vvi vector<vector<int>>
#define rep(i, st, ed) for(int i = st; i < ed; ++i)
// ************************DEBUG START********************************
#ifndef ONLINE_JUDGE  // if ONLINE_JUDGE is not defined (when compiling on our pc, this is true)
//#define cerr cout  // if you want to print to stdout, uncomment this
#include "myprettyprint.hpp" // include myprettyprint.hpp
#else
#define dbg(...) // else, when defined (most modern CP sites have this defined), define dbg(...).
                 // this basically just would do nothing on seeing dbg() and thus no need to remove dbg() while submitting.
#endif
// ************************DEBUG END**********************************
const int MX_LVL=20;
struct edge{
  int x,y,d;
};
struct tree{
  int N, R;
  vvi G,PAR;
  vi LVL;
  void init(int n, int r){
    N=n; R=r;
    PAR.resize(MX_LVL,vi(N,-1));
    G.resize(N);
    LVL.resize(N,1);
  }
  void add_edge(int x,int y){
    G[x].push_back(y);
    G[y].push_back(x);
  }
  void dfs(int x){
    for(auto y:G[x]){
      if (PAR[0][y]>=0) continue;
      PAR[0][y]=x;
      LVL[y]=LVL[x]+1;
      dfs(y);
    }
  }
  void make_par(){
    PAR[0][R]=R;
    dfs(R);
    rep(i,1,MX_LVL) rep(x,0,N){
      PAR[i][x]=PAR[i-1][PAR[i-1][x]];
    }
  }
  int LCA(int x, int y){
    if (LVL[x]<LVL[y]) swap(x,y);
    int d=LVL[x]-LVL[y];
    rep(i,0,MX_LVL) if(d&(1<<i)){
      x=PAR[i][x];
    }
    if (x==y) return x;
    while (PAR[0][x]!=PAR[0][y]){
      for(int i=MX_LVL-1;i>=0;i--) if(PAR[i][x]!=PAR[i][y]){
        x=PAR[i][x];
        y=PAR[i][y];
      }
    }
    return PAR[0][x];
  }
}TREE;

int V,E,K;
vi ORD,DSCV,PRV;
int now=0;
vi BRG, TREE_NODE;
map<pair<int,int>, int> MAP;
vector<vector<pair<int,int>>> G;
vector<edge> EDGE;

vector<int> v;
int root(int x) {
  if(v[x] == x) return x;
  else return v[x] = root(v[x]);
}
void uf(int x,int y){
  if(root(x) != root(y)) v[root(x)] = root(y);
}
int t_node(int x){
  return TREE_NODE[root(x)];
}

void dfs(int x){
  ORD[x]=++now;
  DSCV[x]=now;
  for(auto p:G[x]){
    int y=p.first, idx=p.second;
    if (y==PRV[x]) continue;
    if (ORD[y]) {
      DSCV[x]=min(DSCV[x],DSCV[y]);
      if (EDGE[idx].d==0) EDGE[idx].d=(y>x)?1:-1; //1이면 더 큰 수로 이동하는 간선
      continue;
    }
    PRV[y]=x;
    dfs(y);
    if (ORD[x]<DSCV[y]) BRG.push_back(idx);
    else {EDGE[idx].d=(y>x)?1:-1; uf(x,y);}
    DSCV[x]=min(DSCV[x],DSCV[y]);
  }
}

void solve(){
  cin >> V >> E;
  G.resize(V); EDGE.resize(E);
  rep(i,0,E){
    int a,b;cin>>a>>b;
    G[a-1].push_back({b-1,i});
    G[b-1].push_back({a-1,i});
    edge e={a-1,b-1,0};
    EDGE[i]=e;
  }
  ORD.resize(V); DSCV.resize(V); PRV.resize(V); v.resize(V);
  rep(i,0,V) v[i]=i;
  dfs(0);
  dbg(BRG);
  rep(i,0,E) dbg(EDGE[i].x,EDGE[i].y,EDGE[i].d);
  dbg(v);

  TREE_NODE.resize(V,-1);
  int tmp=0;
  rep(i,0,V) if(TREE_NODE[root(i)]==-1) TREE_NODE[root(i)]=tmp++;

  int N=BRG.size()+1;
  TREE.init(N,0);
  for(auto i:BRG){
    int x=t_node(EDGE[i].x), y=t_node(EDGE[i].y);
    TREE.add_edge(x,y);
    TREE.add_edge(y,x);
    MAP[{min(x,y),max(x,y)}]=i;
  }
  TREE.make_par();

  int Q;cin>>Q;
  while(Q--){
    int a,b;cin>>a>>b;
    int x=t_node(a-1), y=t_node(b-1);
    if (x==y) continue;
    int z=TREE.LCA(x,y),cur=x,prv;
    while (cur!=z){
      prv=cur;
      cur=TREE.PAR[0][cur];
      //prv->cur
      int idx=MAP[{min(prv,cur),max(prv,cur)}];
      int u=EDGE[idx].x, v=EDGE[idx].y, d;
      d=(t_node(max(u,v))==cur)?1:-1;
      if(EDGE[idx].d==0) EDGE[idx].d=d;
      else if (EDGE[idx].d!=d) {cout << "No\n"; return;}
    }
    cur=y;
    while (cur!=z){
      prv=cur;
      cur=TREE.PAR[0][cur];
      //cur->prv
      int idx=MAP[{min(prv,cur),max(prv,cur)}];
      int u=EDGE[idx].x, v=EDGE[idx].y, d;
      d=(t_node(max(u,v))==prv)?1:-1;
      if(EDGE[idx].d==0) EDGE[idx].d=d;
      else if (EDGE[idx].d!=d) {cout << "No\n"; return;}
    }
  }
  cout << "Yes\n";
  for(auto e:EDGE){
    int x=e.x, y=e.y, d=e.d;
    if(d==1) cout << min(x,y)+1 << ' ' << max(x,y)+1 << '\n';
    else cout << max(x,y)+1 << ' ' << min(x,y)+1 << '\n';
  }
}

int main(){
  cin.tie(nullptr)->sync_with_stdio(false);
	solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 2
1 2
2 3
3
1 2
1 3
2 3

output:

Yes
1 2
2 3

result:

ok OK!

Test #2:

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

input:

3 2
1 2
2 3
3
1 2
1 3
3 2

output:

No

result:

ok OK!

Test #3:

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

input:

4 4
1 2
1 3
1 4
2 3
7
1 2
1 3
1 4
2 1
2 3
3 1
3 2

output:

Yes
1 2
3 1
1 4
2 3

result:

ok OK!

Test #4:

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

input:

9990 47670
134 2450
4227 9100
1861 9948
120 8957
1161 4767
76 1714
5207 5838
2726 8974
2489 8619
2379 4933
3675 9554
344 3215
1654 6168
5630 6614
3247 5202
4456 5373
4380 6605
2626 4064
2194 6332
2749 9719
360 5059
7967 8835
5433 6494
497 6638
5945 9063
7576 7879
3550 4107
83 2891
3107 6917
2089 689...

output:

No

result:

ok OK!

Test #5:

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

input:

3219 13421
762 2133
1106 2880
2287 2476
313 992
741 1903
811 2050
1468 2184
3031 3037
403 1855
1060 1415
1792 2804
772 2956
140 2281
808 1953
895 1731
1217 1551
1264 1885
749 1082
1564 2824
1549 1741
1966 2730
112 2825
158 2625
2128 2917
128 3032
644 3194
1634 2743
1545 1961
2402 2680
2663 2814
1040...

output:

No

result:

ok OK!

Test #6:

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

input:

8013 18891
6127 6374
3969 4617
215 2699
268 6282
167 5415
1318 6256
3994 6192
4325 7186
1785 4188
6570 7153
772 5901
9 5190
873 6509
161 7476
2960 2966
4598 7170
1157 3798
758 4508
1446 5205
445 5989
686 5479
669 4711
6254 6860
1722 7020
463 3494
5063 7309
2231 6762
1208 4304
4789 5081
3925 6248
107...

output:

No

result:

ok OK!

Test #7:

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

input:

9968 46595
3655 5544
5747 9340
6020 9528
5789 9882
4609 8832
1969 5167
2610 8012
324 9387
694 3647
3667 8483
4202 4963
2643 8104
1139 9679
1407 7022
9031 9944
5183 8744
3341 3858
326 2610
414 1317
657 7942
4702 5671
2072 3200
3074 3597
26 3728
288 7757
144 9580
1374 2065
2683 8068
1341 6526
2140 257...

output:

Yes
3655 5544
5747 9340
9528 6020
5789 9882
4609 8832
5167 1969
2610 8012
9387 324
3647 694
8483 3667
4963 4202
2643 8104
1139 9679
1407 7022
9944 9031
5183 8744
3341 3858
326 2610
414 1317
7942 657
4702 5671
3200 2072
3597 3074
26 3728
288 7757
144 9580
1374 2065
8068 2683
1341 6526
2140 2570
1488 ...

result:

ok OK!

Test #8:

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

input:

273 1157
172 181
175 181
180 224
42 164
196 252
126 183
32 225
44 138
55 203
71 193
97 180
190 217
229 259
49 221
53 71
32 125
122 168
98 147
209 261
6 245
36 214
134 253
205 223
25 168
167 236
35 164
71 87
7 170
13 36
116 132
147 165
167 254
122 179
83 97
78 172
107 127
12 59
15 242
48 201
225 269
...

output:

Yes
181 172
175 181
224 180
42 164
252 196
183 126
225 32
44 138
203 55
71 193
180 97
190 217
259 229
221 49
53 71
32 125
122 168
98 147
261 209
6 245
214 36
253 134
205 223
168 25
167 236
164 35
87 71
7 170
36 13
116 132
147 165
254 167
179 122
97 83
172 78
107 127
59 12
242 15
48 201
269 225
125 1...

result:

ok OK!

Test #9:

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

input:

7563 11902
923 6491
841 5346
4236 6858
382 7479
3348 6098
1908 5546
564 6550
4767 6536
5181 7272
979 4282
3250 4044
4296 4678
57 5608
1172 3104
849 4089
1936 2337
4111 5978
2091 4188
5286 5313
3866 4426
6111 6585
970 2002
1477 2355
3425 4650
2892 2912
2554 6195
2830 6120
384 3107
4271 5234
629 1319
...

output:

Yes
6491 923
5346 841
6858 4236
7479 382
6098 3348
1908 5546
564 6550
6536 4767
5181 7272
979 4282
4044 3250
4678 4296
5608 57
3104 1172
4089 849
2337 1936
4111 5978
4188 2091
5286 5313
3866 4426
6585 6111
970 2002
2355 1477
3425 4650
2892 2912
2554 6195
6120 2830
3107 384
5234 4271
1319 629
6565 47...

result:

ok OK!

Test #10:

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

input:

8925 13782
1859 2185
5433 7565
6107 7778
1699 5422
2247 5228
3048 6500
996 8342
1063 7629
5648 6266
1827 3051
761 1875
8268 8811
1770 5354
400 8680
1877 7156
2037 3933
1393 6095
904 3022
5109 8078
6775 8153
1612 4288
484 1918
4339 4349
3907 6395
2832 5106
4928 6441
1572 6969
1255 4539
5433 8335
1760...

output:

No

result:

ok OK!

Test #11:

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

input:

492 1768
205 271
267 353
385 421
212 383
87 98
294 385
9 153
166 245
7 55
58 320
409 449
223 423
19 389
90 245
105 392
290 317
121 252
245 317
384 395
3 419
62 254
103 157
295 452
335 358
125 491
14 399
181 257
127 226
334 374
88 207
111 345
147 177
45 405
276 327
127 338
4 241
26 380
54 228
127 235...

output:

No

result:

ok OK!

Test #12:

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

input:

4057 7108
1230 1841
801 3026
1133 2581
319 2719
2986 3702
582 2859
1744 2119
1157 2900
397 3175
2015 3372
2757 3841
1666 1982
988 2371
644 3898
1645 2196
72 2485
689 3637
10 131
170 3108
2987 3354
1666 3705
670 2169
3420 4015
1161 2926
186 1468
667 2299
2639 4009
1221 3004
3955 3961
1816 3089
662 23...

output:

No

result:

ok OK!

Test #13:

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

input:

8853 14008
985 5627
4689 8520
1797 2206
5193 6884
688 7678
3401 8581
5909 8027
5687 7559
3985 6113
179 5352
304 7414
1703 6835
4757 5769
4581 7750
4282 7835
1759 7538
1712 4620
473 6863
1830 8262
3885 4152
459 5868
2777 6144
6716 7265
3103 6296
4516 7641
555 829
5696 6672
2468 8016
1542 4604
5455 69...

output:

Yes
5627 985
4689 8520
2206 1797
6884 5193
688 7678
3401 8581
8027 5909
5687 7559
6113 3985
179 5352
7414 304
6835 1703
5769 4757
7750 4581
4282 7835
1759 7538
4620 1712
473 6863
1830 8262
4152 3885
5868 459
6144 2777
6716 7265
6296 3103
4516 7641
829 555
6672 5696
8016 2468
4604 1542
6976 5455
5254...

result:

ok OK!

Test #14:

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

input:

8426 29348
2004 5877
6189 7733
3413 4009
5325 8070
6622 8102
1108 4909
3956 5682
1299 2475
6692 7065
1960 3899
2353 2830
1694 8139
4008 4939
1660 1913
460 5353
5184 7672
5982 7533
5048 6901
35 1974
2595 6944
3646 5337
5299 6012
1559 1914
658 6185
693 4233
7688 7702
1332 8407
2392 6380
670 7007
845 1...

output:

Yes
2004 5877
6189 7733
3413 4009
5325 8070
8102 6622
1108 4909
5682 3956
1299 2475
6692 7065
3899 1960
2830 2353
8139 1694
4939 4008
1913 1660
5353 460
5184 7672
5982 7533
5048 6901
35 1974
6944 2595
5337 3646
5299 6012
1914 1559
6185 658
693 4233
7702 7688
1332 8407
6380 2392
670 7007
845 1675
122...

result:

ok OK!

Test #15:

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

input:

3999 12704
211 3682
1145 2790
1018 3100
2567 3422
1024 3401
1536 3565
657 3681
1021 3089
1565 3368
696 2032
866 1326
1440 3867
607 3929
1580 3088
1270 3253
1085 2590
877 2611
540 2119
2343 2898
403 2358
901 1356
1651 2914
901 2236
2883 3721
741 859
2172 2975
451 1422
663 1082
56 1277
956 2839
1189 2...

output:

Yes
3682 211
2790 1145
3100 1018
2567 3422
3401 1024
3565 1536
657 3681
1021 3089
1565 3368
2032 696
866 1326
3867 1440
3929 607
1580 3088
1270 3253
2590 1085
2611 877
2119 540
2898 2343
403 2358
901 1356
1651 2914
2236 901
3721 2883
859 741
2975 2172
1422 451
663 1082
56 1277
2839 956
2987 1189
288...

result:

ok OK!

Test #16:

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

input:

10000 70476
2931 5105
4305 5213
5236 6651
2684 5925
3273 7088
7514 7628
3463 3517
2752 7151
763 1751
3603 7655
6963 8831
7886 8872
1443 5160
5771 8328
5164 7431
3903 6396
6633 7356
5312 8917
3950 9909
4610 9606
214 2538
3404 6702
2404 9265
1385 7715
1093 3309
1230 8937
2818 9891
2281 3294
2789 5594
...

output:

Yes
2931 5105
5213 4305
6651 5236
2684 5925
3273 7088
7628 7514
3463 3517
2752 7151
763 1751
7655 3603
6963 8831
7886 8872
5160 1443
8328 5771
5164 7431
3903 6396
7356 6633
5312 8917
9909 3950
4610 9606
2538 214
6702 3404
2404 9265
7715 1385
1093 3309
8937 1230
2818 9891
3294 2281
2789 5594
3579 782...

result:

ok OK!

Test #17:

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

input:

8056 89618
3568 7248
5153 6239
1935 4969
53 3914
6016 7700
912 4039
3518 7847
2444 4847
529 3953
883 1516
2302 8005
92 6599
1252 6829
967 1646
435 3489
109 7308
3393 5250
127 1868
2498 7444
2625 6290
3238 7684
4989 5718
1878 6411
3115 6232
3487 5760
7451 7614
4070 6102
3106 7521
444 6947
1847 2470
3...

output:

Yes
3568 7248
6239 5153
1935 4969
53 3914
7700 6016
4039 912
7847 3518
2444 4847
529 3953
1516 883
8005 2302
6599 92
1252 6829
1646 967
435 3489
109 7308
5250 3393
1868 127
2498 7444
6290 2625
7684 3238
4989 5718
6411 1878
6232 3115
3487 5760
7614 7451
4070 6102
7521 3106
6947 444
2470 1847
3353 560...

result:

ok OK!

Test #18:

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

input:

6678 50741
2438 2575
4259 6116
3096 3605
309 1672
3666 3689
6368 6420
2645 3109
514 2946
1762 5892
3302 4748
1714 3930
416 5773
5881 6344
132 3287
106 1385
1192 6202
1871 5614
1741 2037
85 2227
2202 5460
176 1178
3064 6310
3547 4129
2790 3741
4650 5146
988 4177
1412 2752
3455 5618
1949 2068
632 2863...

output:

Yes
2438 2575
6116 4259
3096 3605
309 1672
3689 3666
6368 6420
3109 2645
2946 514
5892 1762
3302 4748
1714 3930
5773 416
5881 6344
3287 132
1385 106
1192 6202
1871 5614
2037 1741
85 2227
2202 5460
176 1178
6310 3064
3547 4129
3741 2790
4650 5146
4177 988
1412 2752
5618 3455
1949 2068
632 2863
5514 3...

result:

ok OK!

Test #19:

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

input:

1534 6122
382 786
741 744
234 331
39 1179
235 660
910 1480
511 785
900 1191
486 686
1096 1421
94 192
92 1122
729 1447
407 1259
565 759
1131 1384
624 857
178 640
748 860
237 1045
241 485
727 1341
88 1087
754 1440
515 1166
364 1047
956 1322
82 961
60 791
667 1161
198 526
885 938
331 1427
1038 1289
568...

output:

Yes
786 382
741 744
234 331
39 1179
660 235
1480 910
785 511
1191 900
486 686
1096 1421
94 192
92 1122
729 1447
407 1259
759 565
1384 1131
857 624
178 640
860 748
1045 237
241 485
1341 727
88 1087
754 1440
1166 515
364 1047
956 1322
961 82
791 60
667 1161
526 198
938 885
331 1427
1289 1038
835 568
1...

result:

ok OK!

Test #20:

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

input:

6200 15044
2947 5918
2354 5694
2338 3113
4427 4643
1244 2270
1077 2041
1472 2599
1601 3665
1774 5273
664 5573
1797 5265
1312 5196
4866 5803
1544 4331
594 5200
258 1331
1586 1711
1021 2593
307 2836
997 2904
2920 5815
2081 5780
2106 3971
2777 3758
2853 5717
366 985
2258 3592
2389 5933
2422 2843
2078 3...

output:

Yes
2947 5918
2354 5694
3113 2338
4643 4427
1244 2270
2041 1077
2599 1472
3665 1601
5273 1774
5573 664
1797 5265
1312 5196
4866 5803
1544 4331
5200 594
1331 258
1711 1586
2593 1021
2836 307
997 2904
5815 2920
2081 5780
2106 3971
2777 3758
5717 2853
366 985
3592 2258
5933 2389
2422 2843
3178 2078
589...

result:

ok OK!

Test #21:

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

input:

9961 42952
1145 3373
8143 8193
2128 9569
27 5554
144 4783
6315 9422
253 425
5852 6984
3179 3257
5068 7475
2326 5222
1909 5486
1956 8111
2685 9643
3760 6255
1019 5112
4414 4728
4741 8480
2976 7299
1837 4248
2212 4642
5344 9447
6452 9074
4917 9481
132 8681
1562 2225
4077 9137
2151 8626
3710 4808
2012 ...

output:

No

result:

ok OK!

Test #22:

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

input:

4640 8539
1190 2891
166 2489
446 1583
1695 3140
788 2314
2554 3511
798 3938
2209 4123
2021 3901
2404 3464
1569 2657
2290 4282
1548 3942
223 2867
1349 4270
1099 1939
764 868
563 2556
1947 2144
2065 4461
2154 3589
706 1097
3536 3738
310 1901
229 876
972 1320
600 3858
376 557
3049 3510
965 2779
790 158...

output:

No

result:

ok OK!

Test #23:

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

input:

545 835
50 267
333 542
96 160
12 68
266 441
20 222
330 417
408 541
204 453
196 298
72 393
170 328
445 509
231 444
196 526
136 233
97 377
20 400
438 489
97 253
195 359
53 190
137 252
53 373
27 268
18 185
17 91
224 504
407 468
23 80
35 538
171 510
202 343
165 258
445 537
179 393
79 394
359 438
329 399...

output:

No

result:

ok OK!

Test #24:

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

input:

8838 13732
7281 7530
5516 6730
1304 3568
6152 6340
1921 4022
6240 8808
3016 8378
1409 4656
1820 6098
1243 5707
4310 6149
5415 5990
810 7997
589 5582
2147 2526
4710 8109
2421 7006
1841 4073
1038 2335
373 5910
4242 6163
2958 5132
5156 6013
2231 6570
2638 6466
6643 7803
1880 7261
4144 5095
445 5262
199...

output:

Yes
7281 7530
6730 5516
3568 1304
6340 6152
4022 1921
6240 8808
8378 3016
4656 1409
1820 6098
1243 5707
6149 4310
5415 5990
7997 810
5582 589
2147 2526
8109 4710
7006 2421
1841 4073
2335 1038
373 5910
4242 6163
2958 5132
6013 5156
6570 2231
6466 2638
6643 7803
7261 1880
4144 5095
5262 445
1994 2483
...

result:

ok OK!

Test #25:

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

input:

8164 13019
935 2152
2238 5638
1279 5799
2558 7242
6570 7682
119 4527
2379 2905
2683 3531
2117 6717
134 4841
4924 5705
2015 6312
3038 7637
1473 7086
4513 8022
2442 7546
2704 3406
2931 6125
71 897
1442 5794
4550 6416
5091 6516
221 1194
4312 4879
1126 6975
3975 5369
1376 4455
572 1816
3490 8134
2387 60...

output:

Yes
2152 935
5638 2238
1279 5799
7242 2558
7682 6570
4527 119
2905 2379
3531 2683
2117 6717
4841 134
4924 5705
6312 2015
7637 3038
7086 1473
4513 8022
7546 2442
3406 2704
6125 2931
897 71
1442 5794
4550 6416
5091 6516
1194 221
4879 4312
6975 1126
3975 5369
1376 4455
1816 572
3490 8134
2387 6015
3312...

result:

ok OK!

Test #26:

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

input:

6443 10243
484 1945
5630 5799
4552 6202
4033 5271
3357 4683
974 5909
1310 5607
3503 4273
721 4320
4372 4711
3818 4025
1821 2782
8 5408
1867 5572
142 1753
2315 4948
1185 5047
4940 5233
1238 5996
1309 3483
3283 3882
1366 4025
4019 5049
268 4547
483 6111
453 766
5398 5959
3033 5477
58 1950
3325 3763
25...

output:

Yes
1945 484
5630 5799
4552 6202
4033 5271
4683 3357
5909 974
5607 1310
4273 3503
721 4320
4711 4372
4025 3818
1821 2782
5408 8
1867 5572
142 1753
4948 2315
5047 1185
5233 4940
5996 1238
1309 3483
3283 3882
1366 4025
5049 4019
4547 268
6111 483
766 453
5398 5959
3033 5477
58 1950
3763 3325
3414 2527...

result:

ok OK!

Test #27:

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

input:

9364 20205
2847 3723
2332 6026
1231 2542
897 6496
4290 5694
2334 3791
7901 8176
2407 7884
1890 3564
686 2477
1032 3859
8283 8745
105 7215
1788 4223
674 6862
1512 8322
1482 6302
3644 5189
6416 7325
4110 8497
5355 7339
278 3199
747 1241
3970 7568
989 5093
958 6388
4675 5304
7904 9129
6164 9019
4220 49...

output:

No

result:

ok OK!

Test #28:

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

input:

640 947
179 310
246 549
57 559
444 528
246 510
71 283
363 464
117 464
306 309
444 478
52 215
114 377
176 246
420 559
18 283
283 564
143 310
552 619
283 495
415 419
283 460
82 280
17 135
394 465
82 433
3 444
211 310
195 591
493 630
125 253
102 521
132 172
102 215
215 431
92 126
168 362
386 559
246 43...

output:

No

result:

ok OK!

Test #29:

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

input:

5101 7617
3179 4473
2381 4406
264 1538
1496 3356
3655 4392
3435 5036
3010 4599
1025 4272
4073 4392
2131 4112
230 2725
3379 4571
77 2926
2458 3004
243 4934
307 1850
3549 3775
728 742
1105 2901
2099 4986
2157 4811
426 895
2226 4645
651 2781
804 3052
561 4392
474 3227
22 3256
2484 3740
2425 3608
630 31...

output:

No

result:

ok OK!

Test #30:

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

input:

9495 22437
659 2686
189 3206
2686 5140
4350 8162
1248 7355
1527 7151
509 9467
3604 6563
1451 7134
2933 9085
2392 4791
4809 6818
1455 6065
7790 8524
6435 8291
4629 4987
2212 3016
5880 7328
565 7287
2416 5748
3233 4845
2791 5561
4030 7690
4651 4998
33 9086
4469 9102
345 2713
838 7751
814 9298
2077 375...

output:

Yes
2686 659
189 3206
5140 2686
8162 4350
7355 1248
1527 7151
9467 509
3604 6563
7134 1451
2933 9085
4791 2392
4809 6818
6065 1455
8524 7790
8291 6435
4629 4987
2212 3016
5880 7328
7287 565
2416 5748
4845 3233
5561 2791
7690 4030
4998 4651
33 9086
9102 4469
2713 345
7751 838
814 9298
3754 2077
5165 ...

result:

ok OK!

Test #31:

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

input:

672 2622
233 647
531 672
167 301
163 204
11 18
2 102
56 488
29 168
13 506
351 531
69 386
389 643
105 335
43 267
126 536
119 284
172 182
42 165
52 392
2 257
219 322
220 288
251 615
308 665
319 347
339 607
569 657
306 554
369 383
160 332
198 465
170 662
145 177
500 654
270 408
333 537
512 528
386 655
...

output:

Yes
647 233
531 672
301 167
163 204
11 18
2 102
56 488
168 29
13 506
531 351
386 69
389 643
105 335
267 43
536 126
284 119
172 182
42 165
392 52
257 2
219 322
288 220
251 615
308 665
347 319
607 339
569 657
554 306
383 369
160 332
465 198
662 170
177 145
500 654
270 408
537 333
528 512
655 386
245 4...

result:

ok OK!

Test #32:

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

input:

6725 18041
2450 4115
482 1547
4104 5536
4008 4678
3322 4911
111 2471
2065 4707
341 705
1500 5852
165 1828
2162 3369
884 2056
4207 5466
1538 6604
2405 5901
636 2265
958 6475
1973 2885
1074 6131
2974 5222
3393 4143
4432 4703
1753 2662
1389 5845
6096 6685
1025 6696
2743 4555
2064 5831
1593 5692
3715 59...

output:

Yes
2450 4115
1547 482
5536 4104
4678 4008
3322 4911
2471 111
2065 4707
705 341
5852 1500
1828 165
3369 2162
2056 884
4207 5466
1538 6604
2405 5901
636 2265
6475 958
1973 2885
1074 6131
2974 5222
4143 3393
4432 4703
2662 1753
5845 1389
6685 6096
6696 1025
2743 4555
2064 5831
1593 5692
5925 3715
4400...

result:

ok OK!

Test #33:

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

input:

10000 9999
4827 6339
476 2906
3272 9823
3823 7017
309 2978
794 3837
437 7624
7644 7787
1441 4639
3346 4707
3616 7657
2066 5490
1040 7588
2420 4454
3507 4114
764 4601
2195 6334
489 7341
3084 3096
1695 7914
361 9696
3285 3525
4495 6868
349 2044
1374 9003
3734 9160
1885 2149
416 6752
6600 9719
8626 884...

output:

No

result:

ok OK!

Test #34:

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

input:

6451 6450
1410 5169
2175 4341
1056 2980
379 6419
3081 3174
334 3285
4938 5435
2917 4760
5160 6258
5541 6198
870 5260
1934 5630
1470 1812
2243 4554
3690 5325
82 5119
5303 5560
1680 2861
454 5334
158 5926
3318 4681
3753 5089
2519 4686
365 5021
1451 1896
1447 2946
3861 6022
4175 4542
1530 5759
1278 298...

output:

No

result:

ok OK!

Test #35:

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

input:

9380 9379
977 7363
5790 6220
1491 5068
3469 4382
4104 8306
787 1798
2000 5495
658 9342
3764 7860
3677 4821
3193 6786
5620 7850
9374 9376
939 7480
3855 4360
2866 7059
342 6496
7540 8966
2287 9271
1229 1700
4959 6423
2177 8496
153 4908
2267 8715
7417 7495
1523 5532
2612 8499
1746 3880
6824 7171
5560 6...

output:

No

result:

ok OK!

Test #36:

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

input:

10000 9999
2414 5520
7317 8346
2800 4741
1728 3389
412 6320
5689 9612
3614 9580
5427 7278
6903 9593
535 1750
1733 3512
3598 3886
1214 4844
1852 5927
2351 9269
8277 9851
4262 7030
130 4207
2874 3419
3564 4925
3931 7858
8401 8837
64 195
5201 9993
3628 6722
2743 5915
1536 6617
6383 6943
1190 6904
8273 ...

output:

Yes
5520 2414
8346 7317
4741 2800
3389 1728
6320 412
9612 5689
9580 3614
7278 5427
9593 6903
1750 535
3512 1733
3886 3598
4844 1214
5927 1852
9269 2351
9851 8277
7030 4262
4207 130
3419 2874
4925 3564
7858 3931
8837 8401
195 64
9993 5201
6722 3628
5915 2743
6617 1536
6943 6383
6904 1190
8916 8273
93...

result:

ok OK!

Test #37:

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

input:

1888 1887
1355 1401
608 1574
806 1115
131 1880
857 1026
268 1050
20 217
1063 1526
797 1763
1423 1731
329 1391
421 631
131 1492
705 737
163 168
453 836
914 1567
677 1831
289 1562
1001 1828
657 1723
596 1373
1312 1473
19 1738
231 771
376 1098
293 1232
1389 1536
169 244
784 1353
967 1564
477 1863
1808 ...

output:

Yes
1401 1355
1574 608
806 1115
1880 131
1026 857
1050 268
217 20
1526 1063
1763 797
1731 1423
1391 329
631 421
1492 131
737 705
163 168
836 453
1567 914
1831 677
1562 289
1828 1001
1723 657
596 1373
1473 1312
1738 19
771 231
1098 376
1232 293
1536 1389
244 169
1353 784
1564 967
1863 477
1872 1808
1...

result:

ok OK!

Test #38:

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

input:

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

output:

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

result:

ok OK!

Test #39:

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

input:

10000 10000
628 9691
2470 3054
461 8198
1859 5407
674 2080
3141 5461
1633 7779
1276 1404
3532 5399
428 1140
1532 5434
4415 9126
3176 7371
213 7531
8427 9657
3994 9806
1778 2362
1829 4715
5056 8675
5477 7966
471 2420
2098 5548
3080 9573
7529 8371
6669 7586
277 4470
2769 2786
6662 6936
2839 6913
1461 ...

output:

Yes
628 9691
3054 2470
461 8198
5407 1859
2080 674
5461 3141
1633 7779
1276 1404
5399 3532
1140 428
5434 1532
9126 4415
3176 7371
213 7531
9657 8427
3994 9806
2362 1778
1829 4715
8675 5056
7966 5477
471 2420
5548 2098
3080 9573
8371 7529
6669 7586
277 4470
2769 2786
6662 6936
6913 2839
1461 8128
662...

result:

ok OK!

Test #40:

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

input:

4992 4992
918 4909
2359 2915
1144 4961
3134 3302
4164 4691
1707 1816
2129 2417
179 2813
3618 4639
3082 4257
1487 2477
560 4202
1940 3672
1214 3125
1365 2202
1815 2008
740 2200
235 1411
2960 4801
2879 3769
1256 4334
406 3790
273 811
897 1960
1398 2592
2128 4115
563 3729
1497 3509
723 727
985 4320
286...

output:

Yes
918 4909
2915 2359
4961 1144
3134 3302
4164 4691
1707 1816
2129 2417
179 2813
4639 3618
3082 4257
1487 2477
4202 560
3672 1940
1214 3125
1365 2202
1815 2008
740 2200
1411 235
4801 2960
2879 3769
4334 1256
3790 406
811 273
897 1960
1398 2592
4115 2128
563 3729
1497 3509
727 723
4320 985
2864 4149...

result:

ok OK!

Test #41:

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

input:

4619 4619
2943 2996
1204 2384
917 3819
629 2055
4088 4442
3851 4232
1916 3632
2228 4524
2336 2355
310 2728
1242 4010
1158 3656
596 4523
1793 1864
303 835
368 2353
3764 3991
349 1366
1339 2854
1190 3830
1700 3136
3298 3510
789 3898
3642 3832
25 3672
2922 2937
594 942
716 3116
2903 3174
12 1491
201 22...

output:

Yes
2996 2943
2384 1204
917 3819
2055 629
4442 4088
3851 4232
3632 1916
4524 2228
2336 2355
310 2728
1242 4010
3656 1158
596 4523
1864 1793
303 835
2353 368
3764 3991
1366 349
2854 1339
1190 3830
3136 1700
3510 3298
789 3898
3642 3832
25 3672
2922 2937
594 942
716 3116
2903 3174
12 1491
201 2270
432...

result:

ok OK!

Test #42:

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

input:

9999 13331
449 7258
3047 8308
2716 4492
2065 2191
190 2301
1556 6198
2754 6965
3398 3638
2746 7701
6662 7460
1853 4753
195 5712
459 1387
5845 8825
7275 9618
2904 8934
3179 3416
1250 5746
442 5144
1482 4564
846 1484
7023 7580
221 6579
760 1649
1272 5424
4765 6883
5001 5010
1698 7087
1370 3063
2366 68...

output:

Yes
7258 449
8308 3047
4492 2716
2065 2191
190 2301
6198 1556
6965 2754
3638 3398
2746 7701
7460 6662
4753 1853
5712 195
1387 459
8825 5845
9618 7275
2904 8934
3416 3179
1250 5746
5144 442
4564 1482
1484 846
7023 7580
6579 221
760 1649
5424 1272
6883 4765
5001 5010
1698 7087
1370 3063
2366 6858
8415...

result:

ok OK!

Test #43:

score: -100
Time Limit Exceeded

input:

10000 9999
2642 7796
1117 8765
8977 9000
1347 9654
8951 9097
4771 7011
7340 8322
2325 2378
2732 9952
4193 7610
2810 7634
2682 5275
1357 9755
253 2089
3559 7503
5862 8187
2357 4656
2436 7702
202 5523
6454 9747
3290 5300
682 2710
5938 7463
180 6567
7473 9070
5889 7290
1033 3442
2738 3852
2706 5591
723...

output:


result: