## 315 - Network

Moderator: Board moderators

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

### Re: 315 Network

Even toolkit gives wrong output for this problem....

@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

### Re: 315 Network

Getting WA....plzz help

Code: Select all

``````#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<deque>
#include<queue>
#include<map>
#include<sstream>
using namespace std;

typedef long long int L;
typedef unsigned long long int U;

int n;
vector<int>v[110];
int dis[110];
int back[110];
int p[110];
int visit[110];
bool arti[110];
int k;
int c;
int r = 0;
void dfs(int x)
{
visit[x] = 1;
dis[x] = k++;
for(int i = 0;i<v[x].size();i++)
{
if(!visit[v[x][i]])
{
if(x == 1)
r++;
p[v[x][i]] = x;
dfs(v[x][i]);
}
}
}

void art(int x)
{
back[x] = dis[x];
for(int i = 0;i<v[x].size();i++)
{
if(back[v[x][i]] > dis[x])
{
art(v[x][i]);
if(back[x] <= back[v[x][i]])
{
arti[x] = 1;
}
back[x] = min(back[x], back[v[x][i]]);
}
else
{
if(p[x] != v[x][i])
back[x] = min(back[x], dis[v[x][i]]);
}
}
}
main()
{
while(1)
{
scanf("%d", &n);
if(!n)
break;
for(int i = 0;i<=n;i++)
{
v[i].clear();
visit[i] = 0;
arti[i] = 0;
p[i] = -1;
}
string str;
getline(cin, str);
while(1)
{
getline(cin, str);
stringstream ss(str);
int x;
ss>>x;
if(!x)
break;
int y;
while(ss>>y)
{
v[x].push_back(y);
v[y].push_back(x);
}
}
r = 0;
k = 1;
dfs(1);
for(int i = 0;i<=n;i++)
{
visit[i] = 0;
back[i] = dis[i];
}
c = 0;
art(1);
for(int i = 1;i<=n;i++)
{
if(arti[i])
c++;
}
if(r == 1)
c--;
cout<<c<<endl;
}
}``````
-@ce

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 315 Network

brianfry713 wrote:Try running dfs N times, once with each node turned off.
Check input and AC output for thousands of problems on uDebug!

@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

### Re: 315 Network

@brianfry713...i got AC using brute force as u said.
brianfry713 wrote:Try running dfs N times, once with each node turned off.
But whys is the above algorithm not working...any help with that?
-@ce

shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm

### Re: 315 Network

Whats problem in my code, i got wa, help anyone.
I just get the graph then find out the articulation point, if my algorithm is ok then for which input my code failed else whats the algorithm of this problem.
My code

Code: Select all

``````//Templet start
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <list>
#include <algorithm>

using namespace std;

#define sf scanf
#define pf printf
#define long long lld
#define llu unsigned long long
#define fo(i, n) for(i = 0; i < n; i++)
#define of(i, n) for(i = n - 1; i >= 0; i--)
#define mem(n, v) memset(n, v, sizeof( n ))
#define eps 1e-8
#define INF 5000
#define pb push_back
#define maxn 200000+2

#define white 0
#define black 1

typedef vector <int> vi;
typedef vector<vi> vii;

void DFS(int u);
void reset(int n);

vector <int> graph[ 102 ];
int node, edge, k;
int dfs_num[ 102 ], dfs_low[ 102 ], dfsNum, par[ 102 ], articulation_point;
bool ap[ 102 ], vis[ 102 ];
char print[ 102 ][ 32 ];

//Templet end
void input();

int main()
{
//freopen("output.txt", "w", stdout);
input();

return 0;
}
void input()
{
int n, i, u, v;
char ch[ 6 ], garbag;
bool ck;
while(sf("%d", &n) && n)
{
reset(n);

//Get input ************************
for(i = 0; i < n; i++)
{
ck = true;
while( true )
{
sf("%s", ch);
garbag = getchar();
if(ch[ 0 ] == '0') break;

if( ck ) u = atoi( ch ), ck = false;
else
{
v = atoi( ch );
graph[ u ].push_back( v );
graph[ v ].push_back( u );
}
if(garbag == '\n') break;
}
if(ch[ 0 ] == '0') i = n;
}
//********************************
for(k = 1; k <= n; k++)
{
if(!vis[ k ]) DFS( k );
dfsNum = 1;
for(int i = 1; i <= n; i++)
{
dfs_num[ i ] = dfs_low[ i ] = 0;
par[ i ] = -1;
}
}
// Print result *******************
printf("%d\n", articulation_point);
//*********************
}
}
void DFS(int u)
{
dfs_low[ u ] = dfs_num[ u ] = dfsNum++;
vis[ u ] = true;
for(int i = 0; i < graph[ u ].size(); i++)
{
int v = graph[ u ][ i ];
if(dfs_num[ v ] == 0)
{
par[ v ] = u;
DFS( v );
dfs_low[ u ] = min(dfs_low[ u ], dfs_low[ v ]);
if(dfs_num[ u ] == 1 && dfs_num[ v ] > 2 && !ap[ u ])
{
articulation_point++;
ap[ u ] = true;
}
if(dfs_num[ u ] != 1 && dfs_num[ u ] <= dfs_low[ v ] && !ap[ u ])
{
articulation_point++;
ap[ u ] = true;
}
}
else if(par[ u ] != v) dfs_low[ u ] = min(dfs_low[ u ], dfs_num[ v ]);
}
}
void reset(int n)
{
dfsNum = 1;
articulation_point = 0;
for(int i = 1; i <= n; i++)
{
vis[ i ] = ap[ i ] = false;
graph[ i ].clear();
dfs_num[ i ] = dfs_low[ i ] = 0;
par[ i ] = -1;
}
}
``````

Code: Select all

``enjoying life ..... ``

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 315 Network

Try running dfs N times, once with each node turned off.
Check input and AC output for thousands of problems on uDebug!

sbaldrich
New poster
Posts: 3
Joined: Tue Aug 20, 2013 4:49 am

### Re: 315 Network

Just got AC. There are no disconnected graphs in the input as the problem statement says.
From each place it is possible to reach through lines every other place, however it need not be a direct connection, it can go through several exchanges.
Turn off and DFS approach works, however I used Tarjan's algorithm starting from node 0 for each case (which would have failed for inputs such as 5 0 0).

moxlotus
New poster
Posts: 31
Joined: Sat Sep 17, 2011 6:47 am

### Re: 315 Network

brianfry713 wrote:Try running dfs N times, once with each node turned off.
Is that the only way of solving this problem? I am using tarjan's algorithm(iterative). but keep getting WA.
Even after I have handled the 5 0 0 case.

Code: Select all

``````AC
``````
Last edited by moxlotus on Fri Sep 27, 2013 8:16 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 315 Network

Yes this problem can be solved using a simple and easy to code DFS or a correct implementation of Tarjan's algorithm.
Check input and AC output for thousands of problems on uDebug!

moxlotus
New poster
Posts: 31
Joined: Sat Sep 17, 2011 6:47 am

### Re: 315 Network

BrianFry, thanks for the reply. found where my bug is.
Bug: my IO could not handle the trailing space behind each line.
brianfry713 wrote:Yes this problem can be solved using a simple and easy to code DFS or a correct implementation of Tarjan's algorithm.

jakecho1
New poster
Posts: 2
Joined: Mon Feb 10, 2014 4:18 am

### Re: 315: Network

Hey replying roticv, the post almost 10 years ago. In your posted code, the articulation test for root node might be wrong. We are not looking for "if the #no of connections from root node is more than 2". We are looking for if the # of children for root node from the resulting DFS is more than 2.
Also, the test cases might re-iterate one pair of connection more than once.
like:

Code: Select all

``````2
1 2 2 2
2 1
0
0
``````
It is a pitfall for those who want to implement the graph using adjacency list. The test for number of children at root node might fail. We might find multiple children for root node that are pointing to identical nodes in the graph. Just a reminder for people who wasted a lot of time on this problem like me.

vsha041
New poster
Posts: 35
Joined: Wed Feb 12, 2014 10:04 am

### Re: 315: Network

The following test case is wrong because in the problem statement it says that each block ends with a 0 and the entire input itself ends with a 0. So we are missing a zero here.

Invalid Input

Code: Select all

``````1
0
``````
It should be

Code: Select all

``````1
0
0
``````

ilo12
New poster
Posts: 1
Joined: Wed Dec 31, 2014 3:00 pm

### Re: 315 - Network

I'm working on this task since yesterday and still don't know what's wrong in my code

Code: Select all

``````#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>

using namespace std;

struct node{

vector< int > edge;
int low;
int d;
bool art;

};

node graph[105];

int n,t, result;

int DFS(int v, int p)
{
graph[v].d=t++;
graph[v].low=t-1;
for(int j=0;j<graph[v].edge.size();++j)
{
if(graph[v].edge[j]!=p)
{
if(graph[graph[v].edge[j]].d==-1)
{
DFS(graph[v].edge[j], v);
graph[v].low=min(graph[v].low, graph[graph[v].edge[j]].low);
}
else
graph[v].low=min(graph[v].low, graph[graph[v].edge[j]].d);

if(graph[v].d<=graph[graph[v].edge[j]].low)
graph[v].art=true;
}

}
}

int main(int argc, char const *argv[])
{
ios_base::sync_with_stdio(0);
cin>>n;
string line;
while(n!=0)
{
cin.get();
result=0;
for (int i = 0; i < n; ++i)
{
graph[i].edge.clear();
graph[i].d=-1;
graph[i].art=false;
graph[i].low=110;
}
int a, b;
while(getline(cin,line))
{
istringstream ss(line);
ss>>a;
a--;
if(a==-1)
break;
while(ss>>b)
{
b--;
graph[b].edge.push_back(a);
graph[a].edge.push_back(b);
}
}
t=0;
for(int i=0;i<n;++i)
{
if(graph[i].d==-1)
{
int c=0;
graph[i].d=t++;
graph[i].low=t-1;
for(int j=0;j<graph[i].edge.size();++j)
{
if(graph[graph[i].edge[j]].d==-1)
{
DFS(graph[i].edge[j], i);
++c;
graph[i].low=min(graph[i].low, graph[graph[i].edge[j]].low);
}
}
if(c>1)
{
graph[i].art=true;
}
}
}
for (int i = 0; i < n; ++i)
{
if(graph[i].art)
result++;
}
cout<<result<<"\n";
cin>>n;
}
return 0;
}
``````

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 315 - Network

Input

Code: Select all

``````2
1 2
0

5
5 1 2 3 4
0

5
5 3
2 1
4 3
3 4
1 3
0

6
2 1 3
5 4 6 2
0

11
7 9
1 11
4 1
5 11
8 3
3 7
9 3
6 10
10 11 3
2 7
0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4
3 1
1 2
4 2
0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3
1 3
3 1
2 1
0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

11
6 7
11 5
2 5
5 11
10 6
7 4
4 1 6
9 10 5
1 3
8 2
0

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

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

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

5
2 5
5 1
4 3
1 4
0

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

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

45
14 34
6 17
43 41
27 40 37 5 13
8 29
9 41
19 14 42 35 5
30 5
3 31
13 44 3 9
40 14 2
10 43
35 11
18 16 37
17 45
34 33 43 31
16 21
4 6
31 4

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

0``````
Acc Output

Code: Select all

``````0
1
2
2
5
5
4
6
4
9
11
4
7
6
10
9
8
11
11
6
8
9
10
11
14
6
10
6
7
9
12
17
5
3
6
11
6
4
8
8
4
7
11
5
7
5
8
9
5
13
15
10
7
9
2
2
4
10
4
2
5
9
6
5
4
2
2
7
11
3
7
6
10
5
7
1
10
9
7
10
7
8
6
12
5
9
6
6
1
7
8
7
7
15
7
3
3
3
3
13
9
4
``````
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman