315 - Network

[Mukit Chowdhury]

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

[@ce]

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;
	}
}

[brianfry713]

Try running dfs N times, once with each node turned off.

[@ce]

@brianfry713...i got AC using brute force as u said.

Try running dfs N times, once with each node turned off.

But whys is the above algorithm not working...any help with that?

[shuvokr]

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;
    }
}

[brianfry713]

Try running dfs N times, once with each node turned off.

[sbaldrich]

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]

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

[brianfry713]

Yes this problem can be solved using a simple and easy to code DFS or a correct implementation of Tarjan's algorithm.

[moxlotus]

BrianFry, thanks for the reply. found where my bug is.
Bug: my IO could not handle the trailing space behind each line.

Yes this problem can be solved using a simple and easy to code DFS or a correct implementation of Tarjan's algorithm.

[jakecho1]

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]

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]

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]

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

[bradd123]

I solved it using tarjan's algorithm for finding articulation points, jakecho1's post is very helpful.