11504 - Dominos

nbacool2 · Post by **nbacool2** » Mon Aug 11, 2014 11:10 pm

OK, so I made an implementation of Tarjan's algorithm for finding SCCs and if I have an edge from a node to SCC in which it doesn't belong then I do not count that SCC. I tested it on all inputs in the topic and got correct outputs but for some reason i get Runtime Error on the judge. Any Ideas? Btw, on brianfry713's big input my code gave a correct answer in ~7 seconds which I don't know if it's good enough

Code: Select all

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <stack>
#include <utility>
#include <fstream>
using namespace std;
const int MAXN = 100006;
stack<int> S;
vector<int> answers;

vector<int> G[MAXN];
bool visited[MAXN];
int dfs_num[MAXN];
int dfs_low[MAXN];
bool inStack[MAXN];
bool badEdge[MAXN];
int counter = 0;
vector<vector<int> > solution;

void DFS(int root)
{
    //cout<<"root: "<<root<<endl;
    dfs_num[root] = counter;
    dfs_low[root] = counter;
    ++counter;
    visited[root] = true;
    inStack[root] = true;
    S.push(root);
    for(int i = 0; i < G[root].size(); ++i)
    {
        int child = G[root][i];
        if(!visited[child])
        {
            DFS(child);
            dfs_low[root] = min(dfs_low[root], dfs_low[child]);
            if(inStack[child] == false) badEdge[child] = true;
        }
        else if(inStack[child])
        {
            dfs_low[root] = min(dfs_low[root], dfs_num[child]);
        }
        else
        {
            badEdge[child] = true;
            //cout<<"Bad edge from: "<<root<<" to: "<<child<<endl;
        }
    }
    if(dfs_low[root] == dfs_num[root])
    {
        vector<int> SCC;
        int currentNode;
        //cout<<"SCC: ";
        do
        {
            currentNode = S.top(); S.pop();
            inStack[currentNode] = false;
            //cout<<currentNode<<" ";
            SCC.push_back(currentNode);
        } while(currentNode != root);
        solution.push_back(SCC);
        //cout<<endl;
    }
}
bool thereIsBadEdge(const vector<int> &SCC)
{
    for(int i = 0; i < SCC.size(); ++i)
    {
        if(badEdge[SCC[i]]) return true;
    }
    return false;
}
void read()
{
    for(int i = 0; i < MAXN; ++i) G[i].clear();
    memset(visited, 0, sizeof visited);
    memset(inStack, 0, sizeof inStack);
    memset(badEdge, 0, sizeof badEdge);
    counter = 0;
    solution.clear();
    //all ready
    int N, M;
    cin >> N >> M;
    for(int i = 0; i < M; ++i)
    {
        int from, to;
        cin >> from >> to;
        G[from].push_back(to);
    }
    for(int i = 1; i <= N; ++i)
    {
        if(!visited[i])
        {
            DFS(i);
        }
    }
    int count = 0;
    for(int i = 0; i < solution.size(); ++i)
    {
        if(thereIsBadEdge(solution[i]) == false) ++count;

    }
    answers.push_back(count);
}
int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for(int i = 0; i < T; ++i) read();
    for(int i = 0; i < answers.size(); ++i) cout<<answers[i]<<'\n';
    return 0;
}

t.tahasin · Post by **t.tahasin** » Sat Sep 27, 2014 8:43 pm

WA

Tested with all the inputs found in this thread. My program gives the correct output for all the inputs.
Here is my code.

Code: Select all

#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>

using namespace std;


int index;
int scc;
int result;

class Node {
public:
	vector<int> adj;
	int scc;
	int low;
	int index;
	bool curStack;
};

class AnotherNode{
public:
	bool root;
	bool visited;
};

vector<Node> graph;
vector<AnotherNode> sccGraph;

void strongConnect(int v, stack<int> &stak) {
	graph[v].index = graph[v].low = index++;
	stak.push(v);
	graph[v].curStack = true;
	int lim = graph[v].adj.size();
	for(int i = 0; i<lim; i++) {
		int w = graph[v].adj[i];
		if(graph[w].index < 0) {
			strongConnect(w, stak);
			if(graph[w].low < graph[v].low) {
				graph[v].low = graph[w].low;
			}
		} else if(graph[w].curStack) {
			if(graph[w].index < graph[v].low) {
				graph[v].low = graph[w].index;
			}
		}
	}
	if(graph[v].low == graph[v].index) {
		int w;
		do {
			w = stak.top();
			graph[w].scc = scc;
			graph[w].curStack = false;
			stak.pop();
			//printf("%d ",w+1);
		}while(w != v);
		//printf("\nscc: %d\n",scc);
		AnotherNode node;
		node.root = node.visited = false;
		sccGraph.push_back(node);
		scc++;
	}
}


void dfs_visit(int v) {
	int vscc = graph[v].scc;
	sccGraph[vscc].visited = true;
	int lim = graph[v].adj.size();
	for(int i = 0; i<lim; i++) {
		int w = graph[v].adj[i];
		int wscc = graph[w].scc;
		if(wscc != vscc) {
			if(!sccGraph[wscc].visited) {
				dfs_visit(w);
			} else if(sccGraph[wscc].root) {
				sccGraph[wscc].root = false;
				result--;
			}
		} else {
			for(int j = 0; j<graph[w].adj.size(); j++) {
				int k = graph[w].adj[j];
				if(vscc != graph[k].scc) {
					graph[v].adj.push_back(k);
				}
			}
			lim = graph[v].adj.size();
		}
	}
}

int main() {
	int test;
	scanf("%d",&test);
	for(int T = 0; T<test; T++) {
		int n, m;
		scanf("%d %d",&n,&m);
		graph.clear();
		sccGraph.clear();
		for(int i = 0; i<n; i++) {
			Node node;
			node.index = node.scc = -1;
			node.curStack = false;
			graph.push_back(node);
		}
		for(int i = 0; i<m; i++) {
			int x, y;
			scanf("%d %d",&x,&y);
			graph[x-1].adj.push_back(y-1);
		}

		scc = 0;
		for(int i = 0; i<n; i++) {
			stack<int> stak;
			if(graph[i].index < 0) {
				strongConnect(i, stak);
			}
		}

		result = 0;

		for(int i = 0; i<n; i++) {
			int x = graph[i].scc;
			if(!sccGraph[x].visited) {
				sccGraph[x].root = true;
				//cout<<"Not Visited: "<<x<<endl;
				result++;
				dfs_visit(i);
			}
		}
		//printf("result: ");
		printf("%d\n",result);
	}
}

t.tahasin · Post by **t.tahasin** » Tue Sep 30, 2014 4:19 am

No reply...

I am stuck in this problem.

brianfry713 · Post by **brianfry713** » Tue Sep 30, 2014 9:16 pm

http://www.udebug.com/UVa/11504
Click "Critical Input", "Go!"

Suddho · Post by **Suddho** » Thu Dec 18, 2014 12:35 pm

Why below code is getting WA? Need help

Code: Select all

#include<stdio.h>
#include<iostream>
#define MAX 100000
#include <vector>
#include<queue>
using namespace std;

vector<int>edges[MAX];
int visited[MAX]={0};
int level[MAX]={0};
int parent[MAX];


void BFS(int n, int src)
{
	
	//int visited[100]={0};
	

	queue<int>Q;

	Q.push(src);
	level[src]=0;
	visited[src]=1;

	while(!Q.empty())
	{
		int u=Q.front();

		for(int j=0;j<edges[u].size(); j++)
		{
			int v=edges[u][j];
			if(visited[v]==0)
			{
				parent[v]=u;
				level[v]=level[u]+1;
				visited[v]=1;
				Q.push(v);
			}
		}

		Q.pop();
	}

	
}

int main(void)

{
 
	long  N,E,x,y,sze,k,a, in, out, Connected=0,T=0;
	
	scanf("%ld",&T);

	while(T)
	{
	scanf("%ld %ld",&N,&E);

	if(N!=0 && E!=0){
	for(int i=1;i<=E;i++)
	{
		scanf("%ld %ld",&x,&y);

		edges[x].push_back(y);
		edges[y].push_back(x);	
	}

	for (int tt=1;tt<=N;tt++){
		if(visited[tt]==0)
		{
		BFS(N,tt);
		Connected++;
		}
	}
	}

	printf("%d\n",Connected);
	Connected=0;
	

	for(int i=1;i<=N;i++){		
	visited[i]=0;
	edges[i].clear();
	}
	T--;

	}
	
	
	return 0;
}

brianfry713 · Post by **brianfry713** » Wed Dec 24, 2014 12:31 am

Input:

Code: Select all

100
89384 86
73028 22202
21872 59426
5 76035
29766 57218
76556 57267
57804 7315
82703 59996
28955 18709
58249 4805
39729 56068
57550 3520
74843 24407
15348 23551
62824 47452
87747 34898
24051 80311
17304 38342
24993 45922
13755 73644
41526 21710
29024 57262
84210 66281
84989 78679
83483 80116
46799 20806
24325 780
25186 14965
5467 66119
80522 40533
75430 68290
59216 78885
84178 66433
22970 43471
27730 76122
64784 3677
60938 36207
13104 4423
50053 22715
13447 65044
52801 11104
11883 60245
42161 77125
53860 4020
44552 47627
26533 44997
1449 86933
63981 52700
6787 52579
39316 53903
24531 1468
37675 14715
75474 52420
75135 17730
49725 3094
70533 88581
26393 13142
57218 49367
53386 68554
26796 78029
594 64889
62438 20280
72980 2042
21572 3986
24840 46718
15137 27840
9506 49370
12406 19763
37492 51931
55025 54492
53688 54169
67310 3125
52492 47032
26201 35143
23788 16493
81382 19949
7180 80717
49710 21387
81708 47111
4444 71282
9737 17164
33485 75917
6295 19242
38125 45890
67333 43787
64907 3765
6889 87972
73744 91
24302 38228
12657 4388
59080 10425
27053 33926
44064 19628
73434 40467
35260 23275
59574 63086
26178 58892
45085 35755
51444 41728
34730 26009
27365 66153
6372 54780
41419 6134
44361 64751
10771 65721
17777 72393
47950 69850
31109 44830
26928 18269
41544 46175
35516 3819
62710 42749
4759 3325
60428 49426
17067 71579
5619 21414
17825 59807
7572 27366
18373 876
8228 51933
65957 29143
40624 26004
12465 40163
63 71733
44163 39392
43210 41606
25987 21310
24634 47551
38609 30745
43955 11317
48106 55675
57113 49573
18571 7563
8438 64685
58249 36943
7717 32041
58044 50461
32255 48340
61704 70509
51532 32318
15555 32122
68807 20998
10180 41541
72286 19696
46389 48788
46094 57872
33701 36126
43688 29463
35779 52271
30845 67501
25797 20283
70743 38561
28532 25473
37613 44630
3203 16492
63989 15400
51773 18757
60298 684
35755 61953
52372 471
58342 8399
59901 40098
11192 33674
27576 45220
38977 46970
67252 58420
38612 6405
47253 5882
50511 8776
40643 11121
41897 69089
14102 46263
46946 19925
23509 16031
16501 8957
32731 2137
42234 16474
65524 18887
64107 53425
83899 13
2000 29670
66085 14068
55326 67763
2384 62288
57513 11741
81687 369
36708 46294
19698 78122
3691 68
75997 23415
26880 30638
57225 56143
68597 64719
62505 13
9480 34862
41380 41992
55583 4955
26832 41858
17882 45660
2344 41458
8900 19069
46384 9473
23329 60244
53644 20767
32079 884
5519 28564
31734 25814
72891 54
66046 70544
10312 34695
23134 45429
19710 67702
32366 34257
35906 12782
19128 35035
50045 32019
68014 64756
20696 56655
36876 72773
67996 65446
34825 49451
45193 50733
41979 57052
54704 36774
29571 35133
38664 65015
17929 52704
14069 58373
71154 8397
43432 8077
40095 17391
40249 51579
66336 66212
66093 60945
53499 30320
37873 19300
70032 46426
30586 10175
5051 70113
32354 43392
35516 34621
14433 71018
14602 11547
19943 59496
67572 12865
61249 21477
164 65770
17193 28606
47653 66499
54921 41388
60688 28260
32788 19903
61071 15931
13153 63373
33874 66121
27850 3609
1735 27492
39038 385
59880 16337
60195 58980
7566 12664
36536 48552
65101 46
50248 7889
43232 51539
39994 30111
21084 31225
34835 52408
464 20454
24707 35426
27732 57269
22694 22048
23569 10115
13799 58393
58591 15448
22113 59396
55776 55956
46154 63294
9120 22187
11663 34339
64450 55391
21514 54696
42002 20432
43925 59387
29711 45504
40711 6569
28617 60482
8534 63404
56696 52185
5570 22332
16626 53224
44078 27683
28914 7300
32525 28169
62508 41073
31362 44188
33782 61856
20225 55914
50200 13721
62263 64149
5617 17848
16267 37872
36175 37272
27394 24800
50170 30808
18930 32963
63684 4733
15071 945
32152 30536
91522 57
55668 68347
33432 10066
276 72304
85767 66292
57725 82391
43000 87157
38761 27608
45261 74197
37142 85986
79929 72451
35397 76171
48086 13819
60939 33683
36970 33205
24546 8314
65221 36673
46738 80213
49554 87212
61981 35574
26442 43798
27993 16744
32911 69441
40676 55313
49776 78172
47660 77817
51025 26742
29120 83056
13777 7588
40793 78618
75491 50746
75979 53898
42589 49189
44879 19754
55327 80702
32978 3897
20640 81769
48247 60970
13320 53551
40200 88922
63776 63095
78396 87859
67953 23279
19426 15993
83170 81729
29512 48778
11154 67138
13365 13968
33722 53742
42921 46803
50699 77608
56414 64458
22465 71339
33367 13139
90620 35784
87438 62126
47022 51434
63272 74311
19806 50
9708 14845
177 4024
4746 3682
19713 8336
2463 12110
17176 19010
2680 19687
4363 1142
4728 9099
3775 9835
3673 880
14711 5559
7090 12740
15633 15003
10710 14111
9149 15385
1311 2320
7709 11033
19368 7764
67 7615
6819 2024
3613 18950
285 11206
2206 7975
19517 6721
7600 5981
11539 5091
17831 2505
19215 530
16348 13657
10943 11826
14145 5690
16723 13961
1918 2047
11370 17992
1918 1984
2835 18188
9587 5530
15212 3120
9840 11792
19480 14922
207 19147
3553 12920
15157 18037
13595 4669
16495 11698
17388 6439
594 12541
16296 16012
14197 2511
9017 24
7728 1189
2817 352
606 7476
5964 8095
7206 3341
4779 8407
216 3315
2178 1779
2096 290
8864 3540
8035 7892
2827 8948
5336 8483
4394 2083
1919 3573
4761 4326
732 629
4159 7578
2710 1338
4678 1106
495 898
4212 439
7290 5782
2126 2444
98507 15
58215 33536
77989 83743
95839 25753
77648 62594
1768 58820
41850 79733
58776 26672
70671 11446
7110 28851
73308 4205
90579 81334
88581 85927
69700 72201
39523 22629
72471 13507
41893 25
28767 34272
6716 29965
21367 12617
40943 39867
12615 17495
19560 41787
39227 11081
1627 2614
5762 36786
11081 30982
20499 14481
3731 12406
19215 28293
16941 29015
30936 5633
33329 19618
1114 17809
23850 40044
31443 22480
33399 16324
16218 37482
94 11066
13679 13551
1869 1720
26126 19440
80953 17
20801 1167
49449 70342
32382 74170
45548 22468
29749 73793
19338 53767
46125 715
77897 64666
23686 36335
9041 12312
71530 60251
7172 56761
79858 18303
23344 21253
30724 35757
36923 54474
445 8107
94986 57
32322 819
24683 68565
63275 70898
46811 64645
91443 42387
22390 40248
43458 8377
11485 83992
73 56860
68492 83727
42009 73694
77946 57300
46547 68862
3573 20908
70929 56554
57372 7019
75583 63091
39002 41894
11552 43872
46098 85812
85899 62834
71211 68487
17332 89197
51070 42535
31275 17405
50938 79401
41714 33124
6999 33897
14645 88260
49827 65397
72415 45413
13517 67038
13945 12852
16563 52519
3184 80322
48170 62660
90986 89083
83293 79220
81594 13332
85562 94202
78616 17883
10846 41513
35250 25344
73443 17844
43080 49894
320 28284
55161 75335
88186 68663
26195 28946
69107 64588
32261 84204
38140 77116
21189 28260
41591 81272
80487 7797
25679 86992
33519 23957
42660 19
4325 36870
17319 33550
38197 25712
19560 31964
3804 22294
16517 8185
6676 31742
16332 38767
21113 13248
7110 8733
22089 24103
24123 8432
8808 6255
42037 42419
5178 34404
28613 21368
12258 30254
13306 24023
34078 7794
12497 18
4479 9493
644 9768
3207 5680
9567 2914
4374 10789
6781 8313
671 3540
8751 4563
1060 8526
4059 11589
1042 1882
10907 11434
10552 1472
9253 1438
7401 5921
3748 697
10465 11879
5061 4391
49614 91
10913 343
34006 47278
12948 2236
45760 9385
30182 45712
4075 31355
16819 11095
17251 47172
30233 11442
49519 44166
48348 37662
36754 33428
15126 3903
3978 17670
10815 42198
1655 34993
41384 30455
32690 44388
12886 4717
9543 37564
28032 2182
13276 13617
19902 44850
6677 30526
33805 521
46910 15309
7850 41266
45168 34049
10832 22975
24287 49146
43252 21646
2486 25941
29442 35022
48466 43904
40581 1442
3623 8394
30739 18998
14233 16898
6537 1026
10274 29637
44946 49070
40721 16298
732 3181
26156 45003
3648 20292
1051 9556
44224 46899
41034 12265
6554 24051
25492 39886
48279 6248
25245 29114
5125 29403
39157 39477
28227 20390
19845 49430
16113 23558
35467 10951
15067 25573
45864 20736
30291 18714
15999 6028
18292 24900
8064 16146
6417 33573
39820 42284
21783 5082
43212 15450
14040 35636
6411 32754
41298 42267
24938 26255
45933 16524
1210 10790
40253 11386
38827 6187
12215 20929
4942 5211
30085 30506
14465 13006
5675 36501
696 4670
28848 36185
30934 43908
35775 42887
44267 37344
22712 36186
3096 19591
39108 19031
39144 4305
10492 29747
90496 40
72237 82950
45723 71067
32702 43919
2473 53733
65921 57422
9596 81703
60588 70640
36878 48068
71319 29586
83108 36681
89393 81127
87523 64469
22255 61372
9366 79230
16349 37096
15981 85467
66037 88585
42007 48136
11372 85170
52095 30912
22118 77292
43867 61690
19261 69137
8226 67177
13361 84
67642 77765
38169 89185
60060 64668
39833 60424
83951 55858
50828 56181
40702 86364
44003 12800
7473 82708
9555 55374
28602 59567
17192 18104
73672 58900
35580 22885
9400 68330
21932 53
1188 3313
3456 7139
10774 1856
8713 968
20812 2292
2467 14476
8619 17353
9273 709
3071 5287
14041 17099
21183 21688
6611 16700
13904 11042
1299 4143
16466 11747
3191 19037
4243 17654
7641 6646
17677 15016
5439 16353
8896 16557
11977 17970
18678 17514
10932 9381
4548 9880
9635 13104
17935 3798
2971 4378
8520 9907
9785 14334
11438 3053
8838 12976
19621 3812
6959 16478
10898 3498
20054 12397
18498 7925
13570 20162
17675 3376
13255 2569
3804 290
14151 11022
15399 21739
19777 17121
19586 1986
15102 17693
8736 9091
1034 12072
6617 16489
19986 7992
8521 5647
1703 6239
14532 5086
95101 8
41804 68150
42730 85275
43715 34979
40604 89056
33832 42295
64256 71894
67277 68156
8699 40309
33063 3
6298 4926
27721 12832
2263 9074
18835 69
4631 6312
12127 15775
2243 18460
5077 1896
15537 11272
4983 16864
15362 18773
15992 9068
7084 13586
7341 4730
13359 757
16034 17925
6844 13691
6253 13223
1687 14816
2292 14914
731 6317
13653 3296
12903 10685
3121 7606
5634 9604
9541 15815
13759 2160
15745 14409
8015 2008
2764 4251
11052 2539
16229 18797
2061 6772
2752 11359
15149 11459
6653 12755
16050 4756
15440 1470
16788 10117
8597 7438
4417 3586
13458 7014
2587 7053
9060 18079
11206 10602
2017 700
8374 3422
17905 7122
18480 10434
3058 9533
3453 3671
8426 9710
56 8379
7373 12743
1345 5720
9306 15969
4148 13473
1690 11640
10883 14446
13924 18461
326 3254
14387 15940
4227 16411
15721 2334
11866 11583
4130 18778
17364 15318
4862 12556
6463 6297
893 1111
17079 15519
10156 17910
10714 10103
11521 63
5372 3086
1292 7315
5598 2787
1367 5357
10964 9755
6119 6158
5913 11506
3157 3284
6406 724
7937 10887
330 358
10494 2105
10511 3972
4615 9491
8134 5377
8462 1177
8492 9695
960 5942
7488 10278
8511 10037
862 3119
3103 10818
10290 2963
3686 6260
1814 1363
1720 7811
6105 9854
10014 8402
2561 1283
6659 10817
473 10694
8867 11310
5730 5153
3909 6016
4531 1696
4815 8608
4093 5392
8354 7917
10365 2862
4224 8229
707 8368
6700 2133
10534 6811
8093 1381
676 9283
8456 3231
10729 8858
2489 1990
8005 4937
6633 2586
7382 8724
2594 7636
4031 11475
2815 7137
33 10585
7431 3227
5359 739
3739 10319
178 561
9843 8020
11250 853
9711 2966
1145 6646
80570 38
19060 64899
31091 52289
75723 16316
24653 6991
51534 55505
37204 44788
1321 67141
31426 63442
77311 11279
12161 49291
19908 12635
59254 56056
29765 1022
14751 36893
19744 24712
9041 3421
55709 67935
32813 69263
76253 50861
25796 57465
50815 76349
62919 11561
75003 52135
11975 42906
40758 71743
3808 24136
28753 60666
10249 11623
77647 58517
31791 54131
57552 16820
33317 69963
58655 32690
32113 66129
43023 2899
27809 57908
69468 13267
65401 10158
25140 94
15655 2586
5023 12643
1230 17904
23056 16517
20985 598
21200 24674
3375 21485
3777 1631
19813 2071
2259 5343
2904 20585
13322 15502
10610 19512
10061 22631
7183 10591
13468 21076
8870 22837
15600 18782
10158 10099
10696 13807
13632 6002
2639 6755
8678 17006
19077 6707
12342 3350
23934 21335
11988 15537
10200 12407
9897 22598
8340 20261
16488 17371
15067 21807
15448 509
10607 5818
19916 757
6758 21594
3500 8407
273 9688
16395 12177
15818 19641
15835 3596
19132 14611
2169 2683
432 4191
24743 12066
4588 8771
5437 16382
16890 19655
624 21176
21932 2356
24241 20832
4098 3841
13529 2601
14777 4662
24302 5075
8670 5455
20357 15289
18263 2953
7143 22526
9743 18694
2324 7038
23711 14330
9136 8052
4087 15461
18108 9760
5743 1170
5010 17209
19809 9840
14794 18830
23904 9737
15191 14247
4395 7725
10677 10700
8085 22657
16210 18112
301 18119
7600 18825
1736 24011
14331 16736
1647 5822
7283 7591
24799 7389
17520 12585
6274 19759
4355 7465
21712 5330
13346 19838
5397 1258
23915 24023
17286 13773
6751 15276
9253 17586
16748 14350
6237 10988
63559 1
62640 35483
59964 82
1400 59163
31797 39747
55947 47638
58575 59371
46376 44478
12820 39436
5366 14516
55240 17262
53433 29255
524 42890
53452 11469
32901 53776
39930 50028
49743 1054
85 47822
47020 37817
17599 1485
56206 25936
32426 13582
5179 54816
34287 18838
40437 25082
42343 46737
16027 35713
18638 42896
54364 23635
17446 12125
9273 34384
35437 57375
45232 6135
43951 35522
44090 39371
5342 1586
22251 47415
42266 37767
3724 27429
52511 23672
10444 44161
26993 41973
24904 33555
4309 45630
4875 26388
807 21754
26248 21231
27365 43328
25969 11515
57969 18435
20020 17178
4628 3346
48196 42270
16819 46893
17684 59004
43200 16449
58421 35212
15886 10228
2977 30445
56832 20194
41947 14935
43249 4758
55169 8230
26828 10649
29084 21173
38350 24832
35261 56187
45577 50061
44073 30576
29615 9515
25963 1793
37004 19934
37245 24419
54863 52889
13118 40222
2276 58814
10692 2184
17497 45525
3293 5896
34153 44324
16275 39460
35683 19622
9719 51535
22146 28379
37893 911
97509 86
56962 96063
37673 21152
4870 20590
39239 91703
51315 66651
95897 6202
63189 8601
91490 7049
28165 84303
87732 41244
33958 82821
78511 5080
79343 13149
96527 25756
53422 95078
93631 93986
17629 12874
88031 88363
82556 77066
46208 84328
90530 90929
2021 1654
63271 13268
61 93510
37244 91435
33806 44852
49931 28260
41409 14807
95130 86333
40960 94994
48529 51042
20975 91650
82503 66157
2773 11496
95824 67549
60968 48980
7692 45903
59170 62988
16047 70962
21947 16290
61141 10349
38609 55752
27617 68130
14012 37076
89128 25238
33338 54972
49112 40147
63363 54312
65808 34105
4144 66135
72173 21181
67083 22170
85158 79864
53317 83311
2091 58263
68612 32322
45132 20290
88420 64279
3845 72748
55044 59490
16952 50031
90177 88382
45184 23122
57226 56030
79223 68050
46289 18428
40598 53886
36241 70430
56232 82814
626 46616
35996 58322
78612 69237
90574 81127
13424 26581
86070 51477
3998 68468
16399 5513
83202 51234
9754 18641
43750 42919
18405 46036
2412 90038
62959 16061
55933 93220
96894 21681
37061 56559
22836 83
6227 19379
4490 6034
10198 21224
7347 12294
15497 21543
10766 18085
13985 475
16651 12072
3708 15408
13547 10121
18166 15358
2093 15186
17724 6053
20531 10320
22507 16921
4420 21742
18731 5898
18077 8909
21202 6093
18591 2587
11627 13862
14337 6520
9547 16567
9139 21943
183 4211
19568 22685
5990 18349
15357 12616
99 877
8753 13051
2912 22606
19459 13172
13037 12599
9647 14699
8241 2358
7176 5401
2876 10823
4553 21512
11574 3378
7588 13691
4495 2713
21061 18111
7891 10484
2316 13581
17587 7989
21550 11069
15196 20498
10260 9128
14782 5396
7754 10862
16262 13978
1964 5885
18352 10093
13471 6517
20207 7089
757 12014
7289 1866
3305 21817
3517 15179
14123 5621
7645 12059
9721 3793
12920 4
19192 10936
21798 4866
9799 17901
949 6179
7228 11763
18279 19300
17344 11654
831 6605
8470 18101
8037 8119
14253 2731
8351 2510
14568 5540
9332 15995
6954 15244
17136 13207
9028 17101
12165 7053
4187 18827
7753 13113
37542 27
6115 17881
16439 27602
16588 36268
3674 31521
21999 21702
4517 27239
18334 13049
25807 5147
17352 28349
19971 8830
34751 15965
31063 1075
32181 3559
776 35112
3251 13443
31323 29535
19594 9366
1927 10219
35575 30017
8013 5600
32838 13867
20751 12529
11511 7465
35813 9015
11681 28863
7285 12078
6988 8889
82316 34
76025 60574
49372 20576
68909 56795
77588 12764
3534 28732
23907 63190
65644 1881
45633 52569
35611 4229
36302 81222
74076 38014
11552 78656
17655 80498
620 22312
29427 2398
39131 76415
14674 23135
79930 6186
77425 1266
6158 51361
32235 80959
58999 30064
316 74038
78266 80791
79696 12086
26259 32251
4751 71456
69637 37810
36282 80881
963 70257
40515 65708
6527 40093
22439 55188
32614 62616
26235 39
9818 4095
20039 3560
24558 20889
19676 24650
24279 19190
25608 8713
10038 21155
13602 8125
10007 26027
6219 19882
8261 7898
3510 6645
21450 1632
24692 23816
10126 517
13123 24698
2023 19943
23109 15438
13852 8857
1811 25061
7538 20408
15327 1184
9308 17576
25879 11205
4852 1591
9488 14374
3295 21624
5532 12998
19090 24744
7538 12500
10962 2980
5200 20660
18375 12984
21841 2073
898 14503
8675 5928
7111 8435
8287 24001
8971 24931
66995 0
33624 42
33137 11815
11796 5041
22637 15502
9162 5838
28177 3867
1457 1016
2055 7132
21930 6709
24911 20104
25779 8344
5474 7935
8327 10120
27722 4453
10447 14919
14878 13022
5196 7422
26446 14390
10251 16991
22829 15458
19324 19412
787 31365
18856 1141
7849 2841
22944 7161
29488 13119
21054 29083
5578 1337
19773 29380
10674 13659
7040 10580
18001 5911
660 12236
29226 10822
26280 24894
24665 32414
30154 25963
27103 25451
28292 15385
2905 15312
28430 31595
27053 32392
14089 15859
44478 21
20618 16509
3182 42605
16815 29060
1011 9950
26152 29820
12521 11660
2924 33241
39007 43341
7896 12935
21840 20766
29201 34763
6597 17112
12530 9388
24309 32226
31731 20552
40208 33742
35017 11019
40078 43390
12009 7353
40321 41088
11417 38160
92937 31
47028 61071
88283 50124
82037 74798
36918 36248
26984 61111
6610 85161
69612 67819
26835 33948
1781 33108
3299 86864
62883 14405
50693 26684
83768 53559
80986 23184
61460 76158
55903 55312
12498 27161
20632 62859
6169 13208
85929 57549
61383 44763
19645 92539
45160 38058
71165 46479
52016 46940
72955 86074
19820 33572
87131 42322
65505 10650
5481 75179
37553 45638
70912 95
63552 14857
1412 57744
27534 21473
279 23575
63402 66231
4875 65516
15451 42057
64663 43433
58559 14725
68367 38730
52056 32962
70193 7649
7174 63885
68592 43742
57470 60062
4006 7448
9639 65469
31390 5417
28991 37173
47851 31668
26271 36840
23345 68085
40605 41721
893 32455
272 28251
61212 69260
21356 67688
60660 4940
64041 28530
33039 2787
10234 65958
60515 37044
57820 19873
1493 20992
52659 31259
12546 49343
46515 23377
65097 35890
12792 16207
59817 10438
8785 13064
25199 50116
70415 45500
18477 14946
33092 63543
58589 51515
33006 43326
7646 63551
28990 35274
66532 9138
2928 10736
34112 8165
59415 64802
10096 43656
54093 1294
29717 69912
64475 7325
68185 54915
14308 8425
16415 31109
11712 47400
35173 19451
12089 60077
24438 42818
67315 41078
67173 20057
43582 70242
64131 45732
33836 47444
64097 18674
33033 32376
55061 22902
22264 41955
65739 52333
12529 51932
43779 11241
30692 39600
28765 23399
66216 58140
43666 53202
17707 7066
6395 39926
30106 61288
37819 14973
49006 63941
25404 46363
69264 11126
68440 24912
6332 35976
32355 63266
18954 34221
18268 20581
43979 49645
52233 47032
44682 39282
33818 62
29465 29714
4875 25505
27591 13038
15554 19287
13757 20616
23173 10222
16103 2319
13534 18290
30685 20783
12775 8490
4354 22334
4233 3892
1328 32348
29369 32247
26570 25949
21844 4841
23515 22216
28424 26718
12186 17287
4084 10159
20380 25942
21430 20426
31885 2665
16617 28133
2804 28751
10436 29391
26452 327
32674 14668
6266 27779
19909 21394
26234 32835
14403 1104
20991 15930
26386 9008
12336 26346
18470 23639
10246 32716
28550 33069
27384 1482
30232 11348
90 30187
30514 20
7857 26541
13672 22539
10115 14123
13139 33580
27854 29518
11630 20711
29718 15026
7554 31185
21006 8236
303 19193
18443 24421
25903 28852
33369 12008
1547 15486
15505 33458
19350 32060
13950 23362
3666 33021
25953 24064
19764 9974
95258 96
12925 48441
33193 76296
4971 93938
38676 89804
83253 40375
46638 58977
17074 44585
26842 13294
56259 1882
39779 503
56462 35311
40529 85245
25962 75995
74936 41977
47050 83245
49131 91258
72296 72679
71358 95028
89573 89970
35087 27480
86456 77567
26893 94428
25168 8271
22857 66439
79645 81426
21478 75339
65325 40848
21584 74711
34133 8733
9423 13965
9965 81183
58603 58554
58323 94964
7121 47406
74885 65341
60354 42207
54081 66082
87057 4692
71130 79248
65415 27359
7439 55516
13809 4339
79049 85468
94200 35392
62061 30627
16551 8364
79621 84729
1880 87857
52709 55389
25472 9000
63911 32335
15863 85825
7962 22733
6722 20365
60427 79092
39349 72136
89178 80569
70778 65862
18699 72968
8337 82423
8233 80759
70229 37591
42894 87853
60688 72108
93812 344
45382 86159
89429 62464
2642 73948
11758 2132
93927 9363
94202 72184
70199 50722
21325 88122
78535 58422
45587 40023
38228 4317
54612 66523
59117 13198
2752 2247
15294 24546
28150 14009
76472 73379
64773 35024
49860 91817
5921 89234
78864 61232
16695 17568
23135 53804
16967 50723
90746 6412
23432 75257
46521 33715
59616 78043
92993 23084
60333 75071
89079 13028
57097 92
23488 54750
9325 44910
24836 12145
53957 34187
4047 45571
729 2794
44980 45159
23647 24898
54073 36992
8801 30731
16965 31177
38011 37728
49196 40067
23768 1010
55188 35237
32890 7159
52068 13198
16961 33833
10923 19807
56996 13820
8233 6588
43365 628
17144 44831
24725 9915
32264 14119
36914 25144
5774 49228
23816 17827
18837 46588
24728 39203
46361 8546
21743 520
25971 32951
44376 30323
44142 36893
43480 44274
36520 52374
40107 29748
31281 53663
2304 56450
24496 6447
47293 39217
57044 21889
11379 14012
44833 10402
10566 36106
28244 25715
1568 23928
54250 54215
25629 45943
24739 32913
28190 3631
24997 4161
49443 2818
50887 56277
54342 51746
33865 18285
31792 44537
50167 25430
27450 43171
13798 37902
6520 29635
53562 33661
30778 56803
37268 42333
18148 48025
51655 4909
9069 37956
32393 19554
10352 1414
44778 26182
36085 7596
43752 13165
38594 10780
53950 36821
9245 566
30200 2269
35929 7383
55804 18283
3518 1228
49253 35974
40882 21665
51240 35429
54983 41570
34602 26535
52716 56953
56168 13902
27066 31703
42482 42822
14164 181
49462 30953
33222 15027
59347 90
32083 32231
14961 9950
32814 46391
18579 57366
24707 24820
12358 31672
1556 53510
44237 16940
36012 4348
56098 54235
56399 30243
49540 59261
13779 9907
24319 58917
18164 16505
48736 39224
49173 37793
24837 51243
49261 22640
35006 30962
50180 2167
43224 47363
4955 39282
43629 15660
57441 40967
58756 40379
27839 54492
51945 48948
48518 41618
45669 16916
43687 7334
45126 22604
14499 33512
56151 57509
29123 4412
53473 31809
7371 19955
59236 24896
40555 12326
40839 43517
12096 38648
21339 40247
17395 39934
9751 1483
5946 6565
1445 55420
18676 49632
23796 34117
32279 33175
25133 8147
27502 2054
9556 6805
31700 34873
34745 9444
40508 12907
39101 16236
56482 52603
20736 47986
37016 14529
8640 30487
26559 42961
20792 56978
31748 32781
6608 32134
40280 51573
41173 19288
26092 55329
30854 50728
47719 57792
58245 53145
10033 16426
9681 25546
1731 54061
56137 17963
48449 38746
9906 5429
49954 3207
23535 18244
50378 9901
2126 30142
36976 18857
14838 30845
9773 3721
49059 33238
27035 45038
2116 35503
1701 24614
19328 58690
17305 50326
17271 16117
48867 94
4254 22336
1683 10024
41785 40809
33315 47323
36789 813
6457 30139
8830 39790
14899 42821
5089 12297
9368 43520
3659 36938
14455 43016
14525 41527
27886 14687
4027 37886
36888 10366
20390 33815
25756 38570
37026 38841
16321 35737
17009 1614
41403 22777
16730 2505
14802 32968
27621 47352
35422 24169
18317 7946
605 26543
41229 32842
47394 5157
41056 21923
6870 35414
25116 38112
28086 9292
21696 38808
40421 21073
43849 15371
17875 9624
42591 11711
35729 32676
33511 46878
5956 22283
25492 2961
12469 32094
37250 43387
16442 36529
23075 6106
44217 48845
34804 24857
14798 102
21174 7632
48536 31885
41508 41689
30066 17543
1352 11899
9909 16927
15876 34862
14489 41399
24625 41367
35887 3624
40152 38542
21314 28995
5640 39893
15883 16663
42299 17110
1408 7347
39231 40139
32961 1076
18618 8539
20437 14159
31086 45503
8165 7012
48410 46961
16128 48187
2944 835
16043 3147
8808 19762
10788 37356
5151 14447
8223 26670
34016 24116
15388 9630
10705 1046
35118 25015
39173 5990
2625 32221
39233 46925
45019 36323
35643 15442
41810 37813
17626 15253
35014 8985
46340 26433
17547 45801
28586 37
7161 3266
18126 13920
104 16216
8200 17398
14402 21413
20091 26011
3527 16891
12922 969
13946 9173
27388 1650
23016 5858
7400 22727
3714 8148
16306 5937
5888 8636
11901 23816
20165 24064
11694 1440
1268 2698
24111 19893
28333 26685
14989 15615
27599 3274
12446 10341
11990 23974
12261 11248
5388 6420
25583 19661
8027 20117
166 13302
19547 13914
9391 12067
24522 22142
24839 3514
23407 8219
6318 2793
18407 5583
87308 75
4742 56879
34385 3108
44409 43258
60259 60585
54379 1190
61995 71369
75792 27693
11388 50198
30118 70471
60640 85301
25812 24972
33788 51168
34003 24556
86787 82403
77491 34309
35108 474
3581 26152
69409 69492
73996 79217
24327 73587
57647 41067
68759 86321
49210 46131
60521 24067
53287 23248
48219 33852
85019 23018
47574 25926
52249 62941
9942 78280
78753 42431
68582 76277
58460 26254
18162 81911
68189 76375
30133 42488
41500 38528
84658 42812
66878 34630
57877 57870
35641 64084
87101 50015
75940 33351
40212 78594
69565 40880
27230 81381
70349 4930
31183 39732
34334 72728
61794 80572
35752 46442
84969 4619
78658 21171
87028 26238
28027 2147
66230 1516
51530 63667
40938 66022
57308 71390
56189 81149
75221 70792
75721 27339
67070 58261
43680 19595
44087 45323
4456 49393
85239 79838
44928 33345
59582 76588
78734 75876
77391 301
7887 1575
11517 72841
842 48824
42664 12744
59790 18
12268 24286
58326 8594
51600 55165
13585 34949
42494 20280
4545 47243
19265 45390
31630 46049
39654 51934
35210 37903
5614 47418
1476 37503
22984 25736
10015 39577
23237 47618
12113 46775
55368 35504
24661 4431
82468 50
72399 27067
34785 60414
47888 30336
14868 31095
33667 6741
72131 76443
23508 55926
56256 38464
44521 20270
1548 27170
23659 30457
42048 58952
35348 55019
76307 65777
27912 73692
1362 15158
75571 17843
31250 36147
50313 24062
30802 29189
6235 1511
57437 3537
42000 29742
50011 14296
24537 69593
17581 51559
11114 48195
3818 42700
26009 46461
20756 63196
78353 53920
54834 5190
24408 71456
78589 69155
15875 74720
76231 9995
13531 22109
34923 34271
31638 38602
25726 2465
37095 56175
4973 43307
3538 48209
77741 8790
71986 12618
66538 81569
4290 67870
39929 21975
8662 28697
20948 19122
53128 31
44273 20954
4136 914
35447 24839
45219 49134
10008 4041
42655 16526
29594 38056
12514 25616
30394 24658
1074 17855
47132 9843
11049 16539
45167 49125
12686 13378
18746 43339
11164 2369
3282 9890
37968 18540
14545 41968
49248 30058
46583 27792
15959 38774
11262 26288
50946 31712
49566 41655
1609 2131
21910 46810
46046 15897
29275 13948
7398 8843
11211 48020
6754 16
3767 3002
3903 5442
1067 4093
5288 3769
2460 3946
3239 4764
1750 3075
4417 4910
3851 4683
5056 763
768 5024
287 2705
5449 1426
5541 5895
4480 1515
4516 4359
17858 31
9206 1847
2045 4710
4891 15447
12568 1932
3907 17256
12947 16407
1080 7023
11308 1535
5164 16685
4992 16823
5696 12863
10193 11818
13071 6476
7876 8300
8293 9094
10940 14737
13872 11924
9512 7410
3768 905
302 4221
15054 2100
9122 7674
3635 16133
9385 2571
13819 8798
3802 8802
2762 13940
2557 8420
11145 10258
1493 10432
1736 1579
46547 69
45615 43204
32894 20436
12123 26730
35973 4161
7228 29465
43017 22567
15541 24343
3135 3139
28884 25644
16030 20867
31365 30926
8410 20046
124 15135
26993 4496
551 10119
6775 31053
4942 8363
35092 1865
6025 25808
17469 24518
537 21996
46339 13938
25820 16077
3917 11670
32536 16900
10022 19947
2189 26097
41232 27175
31671 11056
21174 30421
14926 40965
2780 27948
29812 19867
7871 37872
24586 44580
20029 25339
1473 33866
12139 28564
40233 36037
6389 16056
44746 34965
14515 25155
5782 387
11442 17943
1816 46196
40614 41360
22760 16741
45352 5590
5658 14769
21545 6675
32014 30243
26305 41573
32333 33486
22975 38444
16696 34762
23180 38108
25459 23638
32768 46438
17833 39984
39633 44209
1218 19648
45132 42443
1485 23978
943 43936
4064 7143
46129 31231
35001 36077
31759 25887
26527 20786
54063 46
34773 50082
43974 17607
35436 41621
44627 15631
44376 51429
38717 19903
5270 14203
35798 11369
53970 30149
33302 30301
47535 10363
7937 10707
35417 40815
31352 49908
19098 18335
21191 757
18363 6645
48265 11101
26731 6573
3938 38829
4668 17044
38084 49492
6797 9938
46924 19818
50118 6703
17065 33000
50544 43589
37179 31839
27684 31898
3007 14467
15223 53619
6201 24198
35298 40423
46995 402
46068 14804
38685 3707
53198 50736
13448 22705
42522 12769
26310 13146
46145 45414
41777 50212
27988 42625
27297 24892
39358 1608
8001 30304
21727 0
32567 74
3273 24040
2921 6393
20734 26916
23861 19003
7666 18392
3859 24216
6528 12742
10758 6056
30656 1861
2095 24088
5828 18984
31001 17223
6427 10199
8435 29297
18729 578
8950 22087
28479 6333
682 11870
15205 978
19369 8874
17422 22870
19944 7559
30513 23949
10142 30701
6553 28602
15018 12236
29458 29280
6911 13452
10181 20217
5126 15345
21763 13241
3906 30974
27176 17675
18652 21486
30359 9813
17014 22352
14243 15213
23494 4390
19423 12188
25121 1068
30202 25975
22687 7572
5355 11424
31640 13929
13606 32434
13107 21098
19504 2801
4807 1344
22829 31011
8256 7790
30142 20621
20165 25270
13991 28716
8336 11091
29057 846
11153 17789
9692 26691
5548 18171
16432 15046
14912 21519
10049 30037
17169 12350
30593 13885
12328 21976
29765 20854
8907 20584
30185 11671
7819 13404
24494 11608
29353 487
18275 5316
32006 7938
26108 27966
27343 4986
21993 30
17618 941
9135 11606
17425 16212
4447 9753
1100 20020
21094 18220
12047 3765
10440 9330
4183 13901
14203 11066
20116 12283
3451 21054
3982 14927
7023 14984
14082 5090
6030 19750
9362 9707
4769 15165
2924 5638
3664 10059
6285 4023
8632 3608
12937 18331
11083 19071
8987 17963
8253 3292
3197 7953
887 12547
6381 7178
12268 7909
67040 1
33674 54174
30645 24
6355 3672
27399 18585
4644 3400
16383 22175
5485 22713
14752 2713
3663 10660
7982 12003
10047 5696
10113 4083
20748 27281
12809 21657
24491 493
21481 8232
23703 21901
25572 14816
28772 30058
28829 17697
9226 28787
20855 14567
12651 10082
16113 333
12335 16313
17380 19467
53348 53
52866 30833
53303 2942
47634 26476
8219 47052
35170 6300
23990 4671
18762 795
3797 21820
44472 31601
47533 51738
3433 41503
17539 4551
16694 18082
20360 41906
36801 28057
45633 14594
4279 23063
49538 45587
26034 51913
44956 4409
49171 47947
35485 15597
24160 1328
32928 26025
11158 2027
43530 27113
31663 14590
19416 47812
36369 35100
9808 39775
41112 6566
29628 42184
21166 45391
30699 12561
16969 47199
28541 9050
24646 52883
862 10677
36701 35549
37575 33790
47646 47859
9100 14500
8964 12704
47803 15259
1686 32076
25385 44355
33190 29541
21583 1664
969 41100
34950 39025
48074 4681
4216 50235
7563 6115
56449 66
21702 13994
54600 44999
5651 35417
14048 8760
25698 50659
37475 56373
14160 42403
40745 30362
43470 24313
41289 24793
43894 6569
30912 43951
19363 40765
49536 18950
27168 35076
54728 17703
6252 54528
33496 2088
10848 17561
17430 47543
53125 42204
28157 54904
34475 10835
40807 18111
48562 27154
39381 25646
13147 36007
25981 13844
32793 38168
16795 24726
42428 9170
7249 20732
22820 54338
15450 46403
43155 39326
25080 32879
36992 39831
56324 2446
26215 15017
42171 46340
15537 18328
3544 25102
38945 34342
16061 29524
3459 20948
35776 38514
8455 51546
49434 48683
38636 36933
19809 14093
52630 31001
14382 44888
47333 38831
3058 19915
9806 22758
46744 50887
25198 31001
14552 50287
29020 7694
34300 36271
23994 32478
27574 19285
11519 32449
12932 26218
45969 50154
30364 32741
84208 63
34104 53577
12787 76942
28392 77799
73585 33514
42987 33582
31979 49782
7844 6558
51987 79919
29325 77749
72333 38455
78750 18044
80871 4754
24296 54667
70893 19486
12365 46182
15551 65620
58353 35237
28827 17105
50618 75512
24885 18204
56753 82372
4721 45631
41341 64596
58136 56707
83930 59434
66245 35028
28550 67239
37697 62907
71160 41613
3586 24381
78769 83525
23321 7904
25008 41681
32985 40915
47886 75625
62556 57869
8060 20430
817 56045
28543 38168
13393 47720
71516 17032
63 79637
47103 15857
46237 37759
50908 34055
22139 38590
46494 45468
2940 45459
2165 71501
51686 35924
82561 38819
59248 30033
1869 6412
33347 60065
23576 19180
36211 46740
42168 10883
15507 25041
62800 78039
27885 50511
4893 18267
63734 50023
41 40154
35281 73
22332 26539
78 7597
8746 31936
21984 26684
1853 2749
3739 3174
686 87
27477 32472
10512 445
402 34752
31864 4611
23963 15396
28975 1835
9664 19511
606 12149
3406 21933
29790 22937
19591 3744
30687 3254
6002 6553
9726 32539
32885 9741
7191 10672
11376 25340
24811 17962
22833 12037
27432 21653
23747 11774
31285 21125
33533 33670
20581 31890
19805 1917
5660 15089
18342 4374
10926 1065
33863 24604
34604 20911
31582 31467
21525 6773
24994 7676
19972 11314
32966 12545
24319 12122
33506 21431
20079 20582
17450 31757
33934 5379
20467 1973
6346 4312
5637 3788
28651 17531
3160 4218
663 27973
35005 35002
7656 22188
33501 24717
1981 27628
4728 31446
17855 26559
12119 3213
35229 2653
8031 29568
31800 33881
3172 28497
32284 3124
20654 8808
13285 25653
18604 24073
23793 13948
854 18327
8023 31449
24055 34614
30778 10003
12928 45
3554 6960
2149 3596
1887 3920
8206 5777
6156 12107
11260 6698
10261 105
9592 3049
5365 12516
11507 5040
9868 9606
12444 7520
1027 7176
3760 1752
11255 5610
11929 113
3068 1881
5160 1149
6285 4954
3492 12725
6495 11800
11904 1823
4231 3187
2774 7928
39 9596
5633 1352
8231 9266
3514 5148
6259 9258
1299 7273
6746 3945
5185 12587
167 9813
1199 10344
9501 6451
4682 4050
5873 2427
5613 3658
10945 9463
5490 8387
9098 10343
6680 11122
2701 3761
12378 10193
4538 8319
29292 91
26238 2187
15119 28704
12480 16572
18622 25049
16839 22884
7766 19139
13380 20971
22901 7762
18176 19624
9438 2899
7872 15430
28510 8894
16182 11661
20659 8803
3918 26583
28769 534
29238 1611
18930 14596
10352 13173
6764 9007
28893 27190
18868 15277
23038 12981
3312 13225
16871 12670
28847 13498
23139 25490
7858 28064
7574 10028
7319 28517
29050 12239
13849 7543
22886 451
13623 4234
13240 3946
2591 21134
7118 12840
26568 22207
6887 1612
15029 588
14833 23757
19954 14583
14102 8679
18706 27812
27036 22423
5369 26772
5023 27541
27992 19965
24198 28656
3309 12322
4164 8893
21732 6648
310 12029
14388 19008
20343 7196
2408 124
15454 5883
15309 22361
21628 263
22685 4722
2950 20119
18368 28801
20221 8720
8083 17067
844 15874
24766 12140
19535 5755
18532 17954
7669 19844
27787 3627
4499 28759
5349 902
24010 19952
20215 20657
26126 17094
7920 14355
14612 531
9250 26287
14809 5540
21414 18081
928 16401
22155 17635
6296 20462
11761 12142
15769 14712
14178 11003
12652 20267
11674 20274
12386 8117
25210 2596
17699 9220
65658 77
62216 41388
44681 64454
60622 54861
34433 54170
26653 10439
63208 59471
11859 8810
18884 58522
7688 30583
36729 56933
39743 49941
42103 35982
49106 28866
15931 23915
36648 64840
33127 40715
39510 33205
22407 12149
58877 27031
37469 49397
35768 19871
21238 35018
20439 40184
5108 40121
23954 20684
4966 41836
4717 63696
26903 47068
63540 53822
45561 35392
10448 34529
2076 13029
25178 49957
11329 17040
58995 10954
30824 41355
10714 29104
3629 52061
19082 23710
44393 1294
35687 43035
33630 41916
23325 40403
21125 53090
22823 13765
48293 1027
14056 33270
10126 50368
59966 31791
42744 14012
55366 53302
16747 467
45085 58637
16688 12933
14226 56724
26658 53638
29895 49912
24656 60287
40277 45778
59542 38338
39365 63099
23269 42176
19444 45978
4668 33394
47406 13751
1394 47411
40435 37113
22650 10698
23630 19861
10927 39337
19875 37855
22108 37584
24771 49769
22446 39321
12001 65047
62487 16329
51063 43923
7129 97
2419 2922
4003 778
973 1587
2027 2247
4171 906
359 1177
4633 5245
4686 4881
4781 6152
2371 6690
158 602
716 5095
5468 5439
327 6107
94 1537
3738 1151
1928 2512
3378 7020
2137 2900
3805 5404
6581 5587
2982 3444
475 3364
2386 538
6507 5255
5856 4036
2001 6665
4254 5851
4829 6749
436 3861
5011 4922
6713 4174
3344 6939
1989 2961
1235 5481
3218 5074
1388 7095
3329 5480
6017 1862
6397 4994
1901 4675
3490 4403
3125 3181
2800 7023
3754 824
5025 3236
6689 1636
725 4608
439 2183
6943 2713
7066 1673
919 3032
1382 1324
2466 4247
1392 6678
4223 1733
6135 3292
6472 6992
6886 2130
2233 1423
3938 3510
4425 128
4015 2777
4959 5149
13 4453
5406 4773
675 7078
553 6324
2721 1336
884 3018
4030 3392
6683 4387
4249 3035
4445 5306
6728 4005
6795 5957
5365 2816
5592 4090
1390 2250
5983 3421
1064 682
7039 4259
2733 1018
2353 462
2759 4733
996 2517
6903 6788
1974 6958
5134 3302
6587 6418
5245 4012
6827 6252
2492 3480
5010 5289
861 3881
4562 3863
992 1924
80099 13
74372 58296
59309 41050
70125 18821
17002 68987
8707 30485
71678 28100
14663 79034
1029 43947
2572 4254
13014 11436
19384 37103
77316 11496
48471 27339
50033 2
44706 38547
8240 30073
77469 65
13913 46136
22197 60026
75177 31946
47386 8463
25574 54280
50826 8169
64768 17498
67178 59965
44343 69877
5083 60337
20061 33644
5578 72403
77309 48053
39972 75963
19619 11197
57332 38926
21483 68032
57010 2059
10522 53691
30501 26926
35094 36095
53592 38358
55354 56894
6333 332
60669 22227
55871 11415
6348 37761
8344 61448
59941 40689
51885 5348
44273 36592
61655 31747
33805 22787
76477 41195
25152 1358
71953 29508
24897 60246
74171 5107
5439 2781
25008 3034
48949 66107
60899 3409
64856 12329
53017 69243
31622 4359
40950 27432
16210 32926
55713 59637
23362 7046
8404 54720
41260 5546
65791 2887
7994 66156
68937 19524
57058 47933
71071 16475
54384 28537
40865 54500
3305 76271
3160 50913
875 34926
24884 1142
60778 51585
58631 3127
14878 41171
39761 3
1093 641
23081 19300
26946 36042
55939 7
46623 46690
1974 19130
22893 18172
37711 35425
17279 44332
41796 20737
54316 26391
71059 30
19722 30446
48909 55954
33069 65495
41107 40237
14562 58793
48182 7163
38267 63009
33906 30925
50071 22273
62992 27973
5109 31842
21176 2655
25160 47033
48822 58382
35308 45679
66515 66246
41531 55029
39856 44364
13542 3540
52723 9903
7456 18494
10443 29845
51161 36113
58385 34739
62711 30172
62013 40708
43362 67820
34184 12129
60902 58912
33531 11946
31126 42
12814 8073
11071 18895
28565 22759
7776 25730
24622 824
9822 27342
2007 6921
21276 29644
30113 16995
19756 14232
5760 9503
2406 13666
16144 1700
13141 25441
9482 19753
27825 1277
12642 14765
29993 239
25969 10080
3373 6642
2857 11934
18854 13195
4182 28459
14327 9004
15705 3169
12671 26552
9091 21464
23163 7546
25456 25235
6331 28773
22520 3812
11046 3029
3267 4035
14114 9913
9024 21705
2513 17487
30681 11881
1683 13836
22839 27332
22970 16010
3905 31013
21350 28111
94186 47
28840 93811
4773 40626
23187 67556
85892 37116
43146 73648
52648 1708
62307 47258
25942 16892
90566 91221
82188 34914
27073 10
68899 74899
18537 85527
41771 14402
38165 6523
57485 71698
18137 67004
91711 62257
5187 41323
72123 83416
85123 48332
52741 30584
4627 10395
7429 35834
27899 52344
9506 46769
27481 54972
46312 78404
92805 3169
61029 88082
22745 88121
18090 24327
86584 40882
39356 15614
4843 48922
3067 17292
5028 47118
14664 12960
48793 60992
19150 22093
26013 76692
37477 28655
64210 53493
13813 40940
86173 19981
13915 74842
56320 14731
81107 29
49181 34892
11372 54834
43897 67474
32526 33004
58605 43010
72340 14581
71260 54321
78716 27133
15353 68501
18341 59392
7329 47523
1784 74560
51624 9821
26392 13450
62007 40934
62217 68991
42717 30080
16446 73588
11875 73005
34907 35362
36334 70479
30084 12530
39662 26486
271 27692
73475 41405
75319 5002
79561 80803
9517 63493
76942 50077
40415 77
34529 3869
20186 3134
12125 9325
4003 15220
29035 9127
19765 27848
12583 30938
16608 277
23524 22483
35761 23276
4611 19471
3511 26323
25537 38087
23574 23127
38451 6677
18337 15408
18541 40357
9266 5899
21119 30665
7168 21060
16284 17530
15844 26933
35001 28866
18726 40243
23104 18109
4956 21863
7770 27714
33177 16259
39385 683
15151 16335
31742 37421
37362 865
6763 17659
7909 14004
35063 27881
12787 22868
17177 10931
7174 28630
28458 11763
37663 33691
15138 11146
6236 9996
26254 30699
39173 39412
23124 25223
30020 13909
14773 22242
39901 34758
8346 29327
16793 15186
38053 10785
29508 37371
25586 14815
34369 4058
37748 13628
32565 39408
8988 20262
10545 6177
5173 35241
27841 17094
31002 36088
17915 17445
19580 13151
2063 17400
32585 27925
6087 26647
23602 38014
12413 2971
7028 16564
37983 14158
13151 12152
40205 37924
3685 22138
24756 10334
27427 16650
12322 12181
37417 25806
42653 7
13081 25254
3057 40724
8646 17640
5421 8840
11970 23774
6466 16676
11334 32544
29297 20
5153 16255
24618 24058
18708 25294
1591 25494
17698 5448
619 25939
5533 15083
4907 230
9559 1279
12013 6751
10949 6728
905 6220
5487 5433
10489 4203
21038 12452
28706 21124
15884 26191
22187 10479
6675 21043
12943 10229
85247 39
38317 17657
82097 22612
80788 10838
21628 5192
9542 41743
73929 54683
49437 30239
82108 84528
16382 21277
47049 17707
6980 32701
45820 173
61185 27935
48128 69537
72645 28277
19462 82884
79025 25714
36551 16312
80279 48094
4589 58178
1143 4573
8340 52046
24855 50579
45384 63976
81682 14765
20995 7185
66134 62190
63653 66814
51103 42071
43876 26533
82946 38500
37742 63337
53177 50252
13098 74293
47223 21737
85085 76462
16789 48365
72472 8177
45682 41643
16156 92
6439 1710
15848 11050
10060 6567
12502 13913
587 1599
14327 11428
4318 5280
4 12204
3327 9643
9987 6441
10392 11803
11973 10236
1832 373
5988 12653
1828 6200
12093 8288
3181 8267
14833 11784
13725 13241
2867 15363
14818 14311
7618 1037
13240 2979
650 7621
14061 4594
241 10636
8899 8296
8668 12213
12893 10730
773 2683
10971 14721
11015 12866
12677 2179
3447 13875
1109 10245
12583 6313
7350 15927
6933 4044
11664 8617
13211 7582
6245 13752
10075 13451
13691 15144
13901 6770
9453 14611
13175 14674
15567 8451
10629 12217
9936 115
14544 14076
8416 15228
14998 10970
15014 15765
8226 5775
1384 10521
8117 5280
6758 11813
10800 6219
12989 4292
6930 8544
11245 6285
14735 8133
4193 14839
2982 13391
15494 2156
1228 1369
366 7754
11546 4253
14211 15379
13928 3615
13078 15595
11251 10072
134 3679
12154 10078
6649 13122
3250 7112
15244 5922
8788 6012
7431 3280
9620 11769
1165 10952
2549 15031
3127 1531
753 2123
5737 1182
4804 2708
12779 6843
14705 4082
2187 12913
14062 14887
5842 13019
2784 5340
33985 86
11818 2624
11905 29972
27064 32264
28702 33013
10519 31640
24620 4858
27716 7265
20261 6744
21046 30417
14630 11472
2822 29387
21703 2898
29832 4452
11441 24882
20183 31354
33977 32302
22806 32001
24796 6413
5440 10401
8055 19513
18887 10475
12257 27192
28452 12617
3565 32517
4520 15512
5430 18194
21091 7342
6310 27133
18029 11454
8822 17750
10583 4227
30744 3330
9743 33388
9803 21554
1598 9699
20174 17858
5581 20484
33100 26947
25478 47
10075 31181
15389 29997
31855 15504
3168 30996
8465 32681
10962 21197
19940 11803
15133 21545
20947 11215
32768 19392
29090 25267
3656 28883
15381 15278
8239 9236
3799 9013
6208 28233
18762 13873
23893 16114
13124 11148
9844 27061
8789 16105
22425 15322
2881 28728
5957 3572
17480 18345
9626 33241
28138 12584
22379 13281
17033 9534
13063 25134
19382 20831
29220 19270
29900 32660
9822 19127
12202 3556
19660 19665
1002 20990
15732 8099
6187 32384
11260 16205
9978 23666
30767 20885
28682 32632
2697 19160
10308 11729
27076 15759
1044 24206
61565 89
9412 61498
48323 50552
33373 60568
34600 38805
14680 3831
36647 61473
60423 26689
20651 54241
436 14762
58628 6302
56973 2249
25925 46555
24408 39631
14463 10545
35002 23293
49908 30623
19609 44413
8532 36665
40586 18098
21929 43131
8156 20383
47071 58575
51250 7013
48456 6156
39140 16802
45733 45518
30507 34547
39294 10092
47318 54915
16642 53757
49496 20754
3601 4984
6766 34221
52318 38815
47062 12468
32850 39363
1489 55217
27346 18355
51193 17856
34657 14236
59754 28767
28430 45506
55597 55377
48726 6159
25032 41350
538 30485
585 39644
12299 30821
34752 34032
46500 3051
7531 20248
40582 17784
1256 9019
26874 6362
47280 17565
46331 26648
10588 10585
4396 39877
11152 4620
11086 53122
48723 1300
40943 38305
7560 49307
48456 53241
21409 42311
27676 33390
16290 28939
3074 6692
13053 44227
226 29948
21712 25449
36033 11673
16667 32299
2035 40429
58667 27818
29118 39802
16542 45824
60247 8495
26853 24101
31529 47137
45643 13378
42316 59204
4330 27050
36393 10506
5570 44064
7948 36619
13408 27281
59580 9097
49525 30074
14386 78
8037 12089
9322 7109
6373 10041
13482 6568
10918 8625
8484 3673
5838 12925
1003 4474
12466 8078
7441 12664
6962 6375
9134 9910
4227 6215
1189 6625
3828 7752
6342 4339
12335 11864
8406 1278
8733 5210
13834 7502
12062 6152
4690 7932
13293 3514
11591 6580
4858 11372
4249 5533
1056 11819
4535 14270
6508 5283
13922 5724
10950 10335
8701 5877
7154 8899
610 2720
10221 1500
7652 57
8876 7897
12298 13229
5423 8671
5656 9502
1537 11168
8600 10792
10675 2592
8762 14023
6248 2796
14019 8297
14174 3699
13485 9221
11940 7829
10217 14094
653 8663
3061 3482
3212 9528
4700 972
11361 9522
6303 10356
6761 12897
1991 1405
1041 3938
6733 10752
4663 8176
11874 7253
2087 5338
13166 10973
10680 529
9191 8996
13365 11332
7362 13139
14110 3079
12600 12061
8918 11972
10483 4517
6809 2181
6118 13361
9726 8737
2526 13738
7493 890
6227 901
84565 82
55972 38316
50048 1732
15236 35570
69292 5064
26433 9101
34931 74175
23927 34889
70584 9120
75239 12646
27299 62310
45587 19656
25375 76929
79780 76354
32509 74455
46934 66005
64282 15776
62034 18341
13872 29765
79355 37232
46332 83164
32735 65749
60599 41224
50344 56661
29268 46618
68889 979
65162 16528
8892 74438
66226 5971
80425 4106
30072 14169
74472 2755
21095 54316
84080 11902
49133 34967
78092 38831
64541 55427
12085 26261
42884 40574
2626 62428
63407 32113
48641 71515
61387 44003
9935 17494
66126 3009
61705 50321
53075 11632
25909 11573
23474 34132
29060 25423
24215 72607
43468 67113
8808 4190
44764 55552
77942 11653
43766 47389
78865 16745
20709 52368
69861 15648
18657 30643
40925 51421
23014 40323
51895 9434
3527 48923
34307 75368
23371 32586
59660 58522
22673 26800
42314 68468
40082 67436
74787 35690
12396 43809
11611 29048
44696 33104
23708 81471
8288 23314
63636 64632
34027 75829
148 75492
26256 82081
74628 78981
12899 49627
76426 49723
61192 6
56606 1155
23813 13001
117 46605
24711 46037
21870 49587
51833 29041
92407 29
74021 84319
56113 74829
56687 55607
50988 17588
68939 28174
62739 33227
39583 16841
84603 37193
18064 30491
24605 31108
55243 28520
73650 4092
63747 68348
67145 89015
84031 25673
72617 58230
40651 28270
46501 36322
16535 59962
50761 60113
932 85473
9906 76124
20909 40515
71005 57134
50866 1598
85149 58234
62325 13701
82049 29016
80655 88697
73192 39
46134 51839
33591 7146
66925 65642
46012 40142
61117 59141
51049 39876
46298 27748
35656 63402
14576 3624
30071 60319
32536 26472
68311 24812
63179 3537
62971 8378
7241 53427
32073 32710
39856 53374
15456 65663
32612 33588
62360 61467
70974 20536
17915 9848
57 44079
47702 53571
10329 57457
53560 47404
41847 12496
16032 48678
26687 1466
54892 5810
38520 33928
56933 56596
49066 48007
51226 72388
60662 51309
41476 40393
19872 28075
72154 59390
9400 19928
94375 19
91944 12438
81368 88843
32398 8603
77710 90575
55289 54802
28824 52593
45005 1646
22145 44957
56619 10600
17653 12824
66481 62576
11918 78553
43702 51877
24216 84378
65729 92485
10548 60786
74730 82774
91377 91915
13216 12752
14086 54
2571 5070
13359 10483
1866 11594
5025 898
12608 3986
2777 355
13579 7740
1815 4147
1320 14084
5196 8118
2040 9302
6423 4554
4001 4829
1486 9255
4441 12423
3406 10727
4605 4493
2000 161
12626 6470
7937 7024
4861 11148
2283 10714
774 4353
1832 4098
9697 13662
8877 4509
9063 11736
2478 12781
5432 10545
8881 1445
9653 7354
11846 9769
9929 172
4123 11327
1747 8468
3011 12060
6169 6607
8441 5294
6873 4424
3999 10272
12262 2483
11700 10357
9052 7238
1179 91
13103 11965
5232 10059
5741 8670
6323 2991
11799 13151
7533 7927
5900 13545
3547 8025
13318 9550
13974 11987
62422 5
2696 60106
50745 13786
15859 30333
61905 56464
60828 41021
42300 51
34479 5601
22219 1808
25139 29543
37143 28475
36968 37563
17415 17965
33096 28944
15367 34185
12358 13481
33537 8224
9505 24866
1944 17819
12886 5286
12212 16357
8808 29387
34987 21415
23223 3738
33280 17657
3831 8813
4075 28122
6538 1250
30194 24241
16125 86
13566 6012
16987 28483
13800 7554
25372 26492
34529 15743
32099 41009
30847 4440
25855 1358
5095 26285
4393 9529
18341 38374
26948 8224
12225 25167
7107 36237
36322 118
8881 23232
12166 10340
17893 25868
12811 25965
41707 3717
5177 7791
12230 34258
38367 38776
22760 40836
10816 1162
42287 27153
38128 29156
14774 29686
47452 22
24702 16949
45380 24644
34035 19118
19905 6769
39953 22520
17936 43803
34561 47167
30024 35312
38671 3155
1150 7447
28924 39
33143 13830
25345 1690
24648 36230
30909 10159
27107 10190
38897 8158
31340 29098
35866 25480
4611 3792
143 32430
36208 22546
99403 64
45409 85498
295 2666
14925 18079
69395 19184
67582 65715
27265 40712
689 49977
5632 72202
84276 7604
45525 54099
13811 21668
2467 78365
16387 6463
9873 64615
86646 37387
42245 52873
55538 32651
50729 42539
61722 70462
36773 39484
80196 48664
98641 82801
55600 245
7849 23633
77731 40472
80903 53373
51099 10902
17364 2730
67345 67485
24232 46000
98873 54587
87237 66476
9611 55007
44830 57327
96810 90096
58121 963
83764 96366
96611 57358
80990 39960
99195 5056
77192 78082
88983 55
2784 28887
96372 25708
71707 70128
44075 21200
87676 71176
45544 50673
8596 16647
26104 90373
91335 24766
40493 84224
60942 94459
53779 56464
61519 61292
39970 72334
72388 58071
86958 48314
74021 93936
64660 83926
24486 65088
55625 28096
78768 31522
66933 1765
57221 84
34274 2326
19980 23875
6888 25706
34048 40800
2822 56133
26742 6375
53637 46142
16309 28807
18540 526
25867 7621
32014 19217
18157 22630
32218 262
8131 28407
10719 56171
1275 33295
57170 8253
33959 41736
25314 6836
26229 31267
37642 48617
37537 52970
45038 54539
18325 17106
45208 6356
25572 44191
30081 20001
40744 6989
35395 5077
4026 48875
24948 9374
17627 25782
10296 45378
52213 51585
46112 35609
47487 21221
37451 26532
44331 27802
8169 25267
52105 5434
12885 53376
36637 40937
47926 42966
11303 20160
11813 46581
55955 15329
4371 21
45399 16360
31205 14667
13536 3651
45353 20095
9888 3801
52085 25583
14110 54218
22913 23514
40150 29475
13191 35797
42023 19566
39725 3895
50475 53326
31915 14798
14818 12469
28828 36285
14212 23477
27128 23293
6649 27748
52030 15259
40841 16536
34014 10154
54149 18212
47686 56926
55984 37078
56643 3655
28031 40785
36889 2407
17204 21285
33753 11582
11128 52503
18759 25842
49134 25339
16347 45886
3923 19043
35578 31638
5052 8025
17732 75
16116 11167
17302 1520
8235 11422
12306 10554
10860 929
11176 16709
1334 12075
12175 6588
12636 14956
493 9400
3910 12468
16277 10515
9969 14172
17148 11874
14353 4422
15588 10155
15082 16145
9834 833
11386 8992
9921 7815
10200 4513
2263 6772
13359 11533
8756 114
9513 11670
6406 12656
8846 16831
13270 4950
16823 1082
8912 12685
8515 16852
15264 6767
11008 9272
532 10773
4264 4661
12582 13860
2899 14463
8263 14844
633 1934
13603 2694
1025 13554
12652 5684
10633 9871
14360 8189
6549 13132
12251 5539
15714 739
10010 13190
6230 8989
17057 13949
13484 13901
10631 11906
12426 2059
3992 4569
10670 13058
8879 3270
8954 11695
7241 3798
15394 1854
661 7276
12815 4210
8356 16319
11776 14204
8868 4042
3666 3682
17582 8192
2366 17150
1476 10481
725 14791
10116 8875
12144 11395
8765 4671
8468 6773
12035 1681
8956 9538
77919 14
20031 13418
14792 14555
73633 11843
41900 34753
1153 5134
65668 73323
8546 39983
73221 20947
53267 15695
20417 55619
4885 27837
45338 63863
67707 26025
8751 11162
24026 39
22813 18283
13063 16613
15657 898
22121 14480
137 8947
6206 23942
11180 7348
15213 3451
2624 19746
5650 11763
299 3820
737 2667
9280 13216
22970 11321
16566 22868
1383 18839
19709 23636
507 14445
4899 19624
4544 22628
6801 5035
20666 19033
6741 17981
13700 11852
23615 9364
21467 19349
22016 8171
21386 6462
17782 15553
22679 20330
23426 10321
18214 35
14479 19109
22990 2979
1580 19377
8669 11791
6797 16664
10618 5309
1418 13537
83562 39
15726 67944
20287 4227
82344 14269
4302 47138
81529 57867
50571 56980
4338 33295
20505 27664
80286 19752
14917 32266
42160 81679
68843 28451
49389 27152
33856 75454
65487 61295
45676 78939
83165 81213
71671 65962
5728 81946
32440 52162
25579 3694
13178 59200
3302 29916
25858 9872
42137 25
81704 16964
45414 60486
63827 66984
35065 70993
48725 14120
69249 16990
74392 10838
52990 68851
43425 62500
7290 34907
14790 52054
27692 32868
62784 27968
37839 30993
94877 10
38393 29163
39551 16688
79046 55930
44164 12353
51923 62168
81675 4755
32819 33317
71651 23453
31459 56469
82489 47154
66616 0
5665 55
4153 5389
5009 2896
3842 4806
4779 3517
3460 31
791 4360
1304 2164
2754 1805
2310 3112
5487 1916
4286 2261
2316 1455
1007 5660
5476 629
316 1813
423 2738
5633 4468
3608 5432
3283 3809
3839 2721
303 1077
2127 3516
4207 493
3604 4880
17 852
3112 2313
2654 4302
4297 4315
4943 3661
4360 2994
66 4145
2948 4782
4548 4585
2728 5442
1385 2165
2129 5453
3303 574
5618 4255
3470 1845
1583 2444
4756 3486
1010 4694
2230 1744
5404 4193
408 395
4539 4098
2102 5025
3944 708
485 984
2036 1006
5345 756
216 4164
1640 2982
3713 168
2611 3996
12440 6
456 6658
1792 4638
1110 7245
9619 8197
12307 5699
2028 2725
99298 71
8631 72104
93794 64842
4644 12624
25193 962
71357 17765
39239 7157
95540 33776
59399 6085
55827 77356
3309 38184
67537 37690
16456 80132
47174 23679
43179 1728
97799 74037
81040 14027
78868 7132
53953 75535
11396 18412
36176 14046
21202 82753
17230 10314
16399 51641
29699 11528
83910 7125
44814 67205
48039 52148
10726 95467
97195 95212
4851 53905
67931 30595
37726 85890
96325 81698
811 91679
6426 42620
60272 71185
81498 61825
14167 77501
23929 32796
74118 78063
45970 42738
29785 19633
50000 28908
24821 40510
94414 82094
13390 29671
16263 97244
14544 51116
77694 47487
90106 49552
21438 19019
15743 51080
63480 37836
5531 64107
42872 22308
65045 79649
34181 23741
52648 94829
70239 19080
1875 12368
42039 254
97498 15265
66380 92499
74885 12743
62294 78973
97991 65692
51671 18632
90665 48633
13441 15853
72358 31095
45643 90510

AC output:

Code: Select all

ree975 · Post by **ree975** » Sun Feb 08, 2015 12:19 pm

I could pass the input on the board, but getting TLE.
Using Tarjan's algorithm find for SCC and use adjacent nodes to count InDeg.
Any advice will be appreciated! thanks!

(comment code is that I tried to use map instead of bool[] to save some time, but seems in vain)

Code: Select all

#include<iostream>
#include<set>
#include<map>
#include<list>
#include<stack>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<vector>
#define DFS_WHITE 0
#define maxN 100010

using namespace std;

class node{
public:
	int parent,num,low;
	bool artiPoint;
	vector<int> adjNodes;
};

class SCC{
public:
	//bool nod[maxN];
	set<int> nodes;
	int in_deg;
	SCC():in_deg(0){
		//for(int i=0; i<maxN; i++) nod[i]=false;
	};
};

node nodes[maxN];
bool explored[maxN];
int lowlow[maxN];
//map<int,int> lowlow;

int countI;

void computeInDeg(int TN){
	for(int i=1; i<=TN; i++){
		if(lowlow[nodes[i].low]==-1) lowlow[nodes[i].low]=0;
		//if(lowlow.find(nodes[i].low)==lowlow.end()) lowlow[nodes[i].low]=0;
		for(vector<int>::iterator it=nodes[i].adjNodes.begin(); it!=nodes[i].adjNodes.end(); it++){
			if(nodes[i].low!=nodes[*it].low) lowlow[nodes[*it].low]=1;
		}
	}
}

void tarjanSCC(int n){
	if(nodes[n].num!=DFS_WHITE) return;
	nodes[n].num=nodes[n].low=countI++;	//countI=1;
	explored[n]=1;
	for(vector<int>::iterator it=nodes[n].adjNodes.begin(); it!=nodes[n].adjNodes.end(); it++){
		if(nodes[*it].num==DFS_WHITE){
			tarjanSCC(*it);
		}
		if(explored[*it])
			if(nodes[*it].low<nodes[n].low) nodes[n].low=nodes[*it].low;
	}
}

void init(int TN){
	for(int i=0; i<TN; i++){
		nodes[i].adjNodes.clear(); nodes[i].low=0;
		nodes[i].num=0;
		explored[i]=false;
		lowlow[i]=-1;	//-1???0(SCC???indeg) 1(SCC?indeg) ??
	}
	//lowlow.clear();
}

int main(){
	int cases, tileNum, lines, a, b;
	char str[100],*pch;
	scanf("%d",&cases);
	while(cases--){
		scanf("%d %d", &tileNum, &lines);
		init(tileNum); 
		while(lines--){
			scanf("%d %d", &a, &b);
			nodes[a].adjNodes.push_back(b);
		}
		for(int i=1; i<=tileNum; i++){
			tarjanSCC(i);
			for(int i=0; i<tileNum; i++) explored[i]=0;
		}
		computeInDeg(tileNum);	//hope it works
		int ans=0;
		for(int i=1; i<=tileNum; i++){
			if(lowlow[i]==0) ans++;
		//for(map<int,int>::iterator it=lowlow.begin(); it!=lowlow.end(); it++){
		//	if(it->second==0) ans++;
		}
		if(ans==0) ans++;
		printf("%d\n",ans);
	}
	return 0;
}

Jinming · Post by **Jinming** » Mon Feb 09, 2015 6:39 am

Hi, I passed all the inputs in this thread, but I keep getting RTE in the OJ. Please help me!

Code: Select all

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

void explore(vector<vector<int> > &graph, vector<bool> &visited, vector<int> &post, int n, int v, int &clock){
	visited[v] = true;
	for (int u : graph[v]){
		if (!visited[u]) explore(graph, visited, post, n, u, clock);
	}
	post[v] = clock++;
}

vector<int> topoSort(vector<vector<int> > &graph, int n){
	vector<bool> visited(n, false);
	vector<int> post(n);
	int clock = 0;
	for (int i = 0; i < n; i++){
		if (!visited[i]){
			explore(graph, visited, post, n, i, clock);
		}
	}

	vector<pair<int, int> > topoOrder(n);
	for (int i = 0; i < n; i++){
		topoOrder[i] = { post[i], i };
	}
	sort(topoOrder.begin(), topoOrder.end());
	reverse(topoOrder.begin(), topoOrder.end());
	vector<int> ret(n);
	for (int i = 0; i < n; i++){
		ret[i] = topoOrder[i].second;
	}
	return ret;
}

void mark(vector<vector<int> > &graph, vector<bool> &visited, int v, int n){
	visited[v] = true;
	for (int u : graph[v]){
		if (!visited[u]) mark(graph, visited, u, n);
	}
}

int count(vector<vector<int> > &graph, vector<int> &topoOrder, int n){
	vector<bool> visited(n, false);
	int count = 0;
	for (int v : topoOrder){
		if (!visited[v]){
			count++;
			mark(graph, visited, v, n);
		}
	}
	return count;
}

int main(){
	int T;
	cin >> T;
	while (T--){
		int n, m;
		cin >> n >> m;
		vector<vector<int> > graph(n);
		for (int i = 0; i < m; i++){
			int a, b;
			cin >> a >> b;
			graph[a - 1].push_back(b - 1);
		}
		vector<int> topoOrder = topoSort(graph, n);
		cout << count(graph, topoOrder, n) << endl;
	}
	return 0;
}

brianfry713 · Post by **brianfry713** » Tue Feb 10, 2015 2:21 am

ree975, read this thread.
Jinming, instead of vector<vector<int> > graph(n), use a global vector<int> graph[100000], clear it between test cases, and you will get AC.

Jinming · Post by **Jinming** » Wed Feb 11, 2015 2:55 pm

brianfry713 wrote:ree975, read this thread.
Jinming, instead of vector<vector<int> > graph(n), use a global vector<int> graph[100000], clear it between test cases, and you will get AC.

I got AC! Thank you so much brianfry!

dibery · Post by **dibery** » Fri Aug 21, 2015 7:35 pm

Got runtime error. Please help me, thanks.

My approach is tarjan's algorithm. (SCC)

Then count the number of SCC whose in-degree is 0.

I ran through thousands of cases on my computer, but none crashed.

Code: Select all

Got AC.

The reason of RE was stack overflow.

I created 100,000 vectors and int arrays.

Though declaration passed the stack limit, a stack overflow occurs at DFS part because the recursion is too deep.

(Local variables took too much stack memory.)

OJ Board

11504 - Dominos

Re: 11504 - Dominos

Re: 11504 - Dominos

Re: 11504 - Dominos

Re: 11504 - Dominos

Re: 11504 - Dominos

Re: 11504 - Dominos

Re: 11504 - Dominos

Re: 11504 - Dominos

Re: 11504 - Dominos

Re: 11504 - Dominos

Re: 11504 - Dominos