10004 - Bicoloring

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

anup10.duet
New poster
Posts: 8
Joined: Thu Jun 27, 2013 9:21 am
Location: Bangladesh

uva 10004,why WA? Please help me........

Post by anup10.duet » Thu Jun 27, 2013 4:55 pm

Code: Select all

#include<stdio.h>
#include<string.h>
void cycleCheck(int node1);
int visited[250],counter1,numberOfNode,g[250][250],cycle;
int main()
{
    int numberOfEdge,index1,index2;
    while(scanf("%d",&numberOfNode) == 1)
    {
	cycle = 0;
	if(numberOfNode == 0)
	    break;
	scanf("%d",&numberOfEdge);
	memset(g,0,sizeof(g));
	memset(visited, 0, sizeof(visited));
	for(counter1 = 0;counter1 < numberOfEdge;counter1++)
	{
	    scanf("%d%d",&index1,&index2);

	    g[index1][index2] = 1;
	    g[index2][index1] = 1;
	}
	cycleCheck(0);
	if(cycle == 1)
	{
	    printf("NOT BICOLORABLE.\n");
	}
	else
	    printf("BICOLORABLE.\n");

     }


    return 0;

}
void cycleCheck(int node1)
	{
	    visited[node1] += 1;
	    for(counter1 = 0;counter1 < numberOfNode;counter1++)
	    {
            if(g[node1][counter1] == 1)
            {
                g[node1][counter1] += 1;
                g[counter1][node1] += 1;
                if(visited[counter1] == 1)
                {
                    cycle = 1;
                    break;
                }
                else
                    cycleCheck(counter1);
            }
	    }
	}

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

Re: uva 10004,why WA? Please help me........

Post by brianfry713 » Fri Jun 28, 2013 12:03 am

Input:

Code: Select all

4
4
0 1
1 2
2 3
3 0
0
AC output:

Code: Select all

BICOLORABLE.
Check input and AC output for thousands of problems on uDebug!

anup10.duet
New poster
Posts: 8
Joined: Thu Jun 27, 2013 9:21 am
Location: Bangladesh

Re: uva 10004,why WA? Please help me........

Post by anup10.duet » Fri Jun 28, 2013 3:07 pm

thank's a lot brianfry713 , I understand my mistake.

anup10.duet
New poster
Posts: 8
Joined: Thu Jun 27, 2013 9:21 am
Location: Bangladesh

Re: uva 10004,why WA? Please help me........

Post by anup10.duet » Mon Jul 01, 2013 11:42 pm

got AC!!!!!!!! thanks a lot brianfry713.

brosa92
New poster
Posts: 1
Joined: Thu Oct 17, 2013 9:16 pm

Re: 10004 - Bicoloring

Post by brosa92 » Thu Oct 17, 2013 9:31 pm

I've sent the following code and got WA. Anyone can help me w/ that?

Code: Select all

#include <iostream>
#include <string.h>
using namespace std;

#define _N 205

int adjacencyMatrix[_N][_N];
int color[_N];
int n;

bool dfs(int v, int colorToPaint = 1) {
	color[v] = 1;
	int nextColor = colorToPaint==1?2:1;
	int returnValue;
	for (int i = 0; i < n; ++i) {
		if (adjacencyMatrix[v][i]) {
			if (!color[i]) {
				returnValue = dfs(i,nextColor);
			} else if (color[i] == colorToPaint) {
				return false;
			}
			
			if (!returnValue) return false;
		}
	}
	
	return returnValue;
}

bool isBicolorable() {
	return dfs(0);
}

int main() {
	int l, u, v;
	while (cin >> n) {
		if (n == 0) break;
		cin >> l;
		for (int i = 0; i < n; i++) memset(adjacencyMatrix[i], 0, n*sizeof(int));
        memset(color, 0, n*sizeof(int));
        
		for (int i = 0; i < l; ++i) {
			cin >> u >> v;
			adjacencyMatrix[u][v] = adjacencyMatrix[u][v] = 1; 
		}
		
		if (isBicolorable()) {
			cout << "BICOLORABLE." << endl;
		}  else {
			cout << "NOT BICOLORABLE." << endl;    
		}
	}
	return 0;
}
INPUT:
3
3
0 1
1 2
2 0
9
8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
4
4
0 1
1 2
2 3
3 0
5
5
0 1
1 2
2 3
3 4
4 0
3
3
0 1
1 2
2 0
9
8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0
OUTPUT:
NOT BICOLORABLE.
BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.

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

Re: 10004 - Bicoloring

Post by brianfry713 » Fri Oct 18, 2013 7:39 pm

Try the I/O in this thread.
Check input and AC output for thousands of problems on uDebug!

musfiqur.cse
New poster
Posts: 10
Joined: Tue Dec 03, 2013 8:48 pm

Re: 10004 - Bicoloring

Post by musfiqur.cse » Sun Sep 28, 2014 5:20 pm

I am getting WA .. where is the bug in my code..

Code: Select all

#include<bits/stdc++.h>
using namespace std;
#define PI acos(-1.0)
#define ll long long
#define mem(a) memset(a,0,sizeof(a));
#define M 10000007
int visit[10001],matrix[1000][1000],col[100001],chk;
bool phk;

void dfs(int p)
{

    int i,a,b,j;
    for(i=0;i<p;i++)
    {
        visit[i]=1;
        if(col[i]==0)
            chk=1;
        else
            chk=0;
        for(j=i+1;j<p;j++)
        {
            if(matrix[i][j]==1)
            {
                if(col[j]==col[i]&&visit[j]==1)
                    phk=false;
                else
                {

                    visit[j]=1;
                    col[j]=chk;
                }
            }
        }
        if(!phk)
            break;
    }
}






int main()
{
ios_base::sync_with_stdio(0);

int n,m,k,l,i;
while(cin>>n)
{
    if(!n)
        break;
        phk=true;
    cin>>m;
    mem(matrix);
    mem(visit);
    mem(col);
    for(i=0;i<m;i++)
    {
        cin>>k>>l;
        matrix[k][l]=1;
        matrix[l][k]=1;
    }
    dfs(n);
  if(phk)
    cout<<"BICOLORABLE."<<endl;
  else
    cout<<"NOT BICOLORABLE."<<endl;

}


return 0;
}









Shihab
New poster
Posts: 33
Joined: Thu Jun 13, 2013 1:19 pm

Re: 10004 - Bicoloring

Post by Shihab » Wed Oct 08, 2014 9:20 am

wa help

Code: Select all

/*------------------------------------------------*/
//Uva Problem No:
//Problem Name   :
//Type                       :
//Author                   : shihab
//University               : DIU
/*------------------------------------------------*/

#include<map>
#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>
using namespace std;

int main()
{

    int i,j = 0;
    //FILE *fp,*op;
//    fp = fopen("Input.txt","r");
    //op = fopen("output.txt","w");
    int a,n,u,v;
    bool graph[202 ][202];
    int color[202];
    //queue<int>nodes;

    while( scanf("%d",&n ),n!=0 )
    {
        scanf("%d",&a);

        for( i = 0; i < 201 ; i++ )
        {
            color[ i ] = 0;
            for( j = 0; j < 201; j++ )
            {
                graph[i][j] = false;
            }
        }
        i = 1;
        while( i <= a )
        {
            scanf("%d %d",&u,&v);
            graph[u][v] = graph[v][u] = true;
            i++;
        }
        int f = 1;
        for( i = 0; i < 201 ; i++ )
        {
            for( j = 0; j < 201; j++ )
            {
                if( graph[ i ][ j ] == true )
                {
                    if( !color[ i ] )
                        color[ i ] = -1;
                    if( !color[ j ] )
                        color[ j ] = color[ i ] * -1;
                    if( color[ i ] == color[ j ] )
                    {
                        printf("NOT BICOLORABLE.\n");
                        f = 0;
                        break;
                    }
                }
            }
            if( f == 0 )
            {
                break;
            }
        }

        if( f )
            printf("BICOLORABLE.\n");
//        nodes.clear();
//        nodes.push( 0 );
//
//        while( !nodes.empty() )
//        {
//            int h = nodes.pop();
//            color[ h ] = 1;
//            for( i = 0;i < n; i++ )
//            {
//
//            }
//
//        }
    }
    return 0;
}


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

Re: 10004 - Bicoloring

Post by lighted » Wed Oct 08, 2014 9:48 am

Your code fails some random input here. http://www.udebug.com/UVa/10004
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Shihab
New poster
Posts: 33
Joined: Thu Jun 13, 2013 1:19 pm

Re: 10004 - Bicoloring

Post by Shihab » Wed Oct 08, 2014 10:24 am

4
3
1 2
1 3
2 3
how this is bicolorable? pls explain

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

Re: 10004 - Bicoloring

Post by lighted » Wed Oct 08, 2014 11:02 am

the graph will be strongly connected. That is, there will be at least one path from any node to any other node.
According to problem description inputs below from random input of udebug are invalid.

Code: Select all

4
3
1 2
1 3
2 3

6
4
0 3
1 2
1 4
2 3
0
Try input

Code: Select all

5
4
0 3
1 2
1 4
2 3
0
Acc Output

Code: Select all

BICOLORABLE.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

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

Re: 10004 - Bicoloring

Post by brianfry713 » Wed Oct 08, 2014 8:24 pm

I changed the random input at:
http://www.udebug.com/UVa/10004
to this input:

Code: Select all

10
31
0 1
0 3
0 4
0 5
0 6
0 7
0 8
0 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 3
2 4
2 5
2 8
2 9
3 4
3 9
4 5
4 6
4 7
5 6
5 7
5 8
6 8
6 9
11
29
0 1
0 4
0 9
1 2
1 5
1 8
2 3
2 6
2 7
2 9
2 10
3 4
3 5
3 6
3 7
3 8
3 10
4 7
4 8
4 10
5 6
5 7
5 8
5 9
5 10
6 9
7 9
8 10
9 10
5
7
0 1
0 2
0 3
0 4
1 2
1 3
3 4
9
26
0 1
0 2
0 3
0 4
0 6
1 2
1 3
1 4
1 5
1 7
1 8
2 4
2 5
2 6
2 8
3 4
3 6
3 7
3 8
4 5
4 6
4 7
5 8
6 7
6 8
7 8
15
58
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 9
0 10
0 14
1 2
1 4
1 6
1 8
1 9
1 10
1 11
1 12
1 14
2 3
2 4
2 5
2 8
2 9
2 10
2 12
3 5
3 7
3 8
3 11
3 12
4 8
4 9
4 10
4 13
5 6
5 7
5 11
5 13
6 7
6 9
6 10
6 11
6 12
6 13
6 14
7 8
7 11
7 13
7 14
8 10
8 13
8 14
9 13
10 11
12 13
12 14
13 14
4
5
0 1
0 3
1 2
1 3
2 3
13
57
0 1
0 2
0 3
0 4
0 5
0 7
0 8
0 9
0 10
0 11
1 2
1 3
1 4
1 5
1 6
1 7
1 9
1 11
1 12
2 3
2 8
2 9
2 11
2 12
3 4
3 5
3 9
3 10
3 11
4 7
4 8
4 10
4 11
5 6
5 7
5 8
5 9
5 10
5 11
5 12
6 7
6 8
6 9
6 10
7 9
7 10
7 12
8 9
8 10
8 11
8 12
9 10
9 11
9 12
10 11
10 12
11 12
14
46
0 1
0 2
0 6
0 8
0 9
0 13
1 2
1 3
1 4
1 6
1 8
1 9
1 10
2 3
2 4
2 5
2 8
2 12
3 5
3 7
3 8
3 10
3 11
4 5
4 7
4 9
4 10
4 11
4 13
5 6
5 9
5 12
5 13
6 7
6 9
6 10
6 12
6 13
7 8
7 9
9 10
9 11
9 12
9 13
10 11
10 12
6
11
0 1
0 2
0 3
1 2
1 4
2 3
2 4
2 5
3 4
3 5
4 5
12
33
0 1
0 2
0 4
0 5
0 6
0 7
0 9
0 10
1 3
1 10
2 3
2 5
2 6
2 8
2 9
2 10
2 11
3 4
3 5
3 7
3 11
4 6
4 8
4 10
5 9
5 11
6 7
6 11
7 10
7 11
8 9
9 10
10 11
1
0
6
9
0 1
0 4
0 5
1 2
1 3
1 4
2 3
2 5
3 5
4
3
0 1
1 2
2 3
15
60
0 1
0 2
0 3
0 5
0 6
0 10
0 11
0 13
1 3
1 4
1 8
1 9
1 10
1 11
1 13
1 14
2 3
2 5
2 7
2 9
2 11
3 6
3 8
3 9
3 10
3 11
3 13
3 14
4 7
4 8
4 10
4 12
5 6
5 9
5 10
5 11
5 14
6 9
6 10
6 11
6 12
7 8
7 10
7 11
7 12
7 13
7 14
8 10
8 13
8 14
9 12
9 13
9 14
10 11
10 13
10 14
11 12
11 14
12 13
12 14
18
84
0 1
0 3
0 5
0 7
0 8
0 14
0 15
1 2
1 3
1 4
1 7
1 8
1 9
1 10
1 11
1 13
1 15
2 3
2 5
2 6
2 9
2 11
2 12
2 15
2 16
3 6
3 9
3 13
3 15
3 16
3 17
4 5
4 8
4 9
4 11
4 13
4 15
4 16
4 17
5 6
5 10
5 13
5 15
5 16
6 7
6 10
6 11
6 12
6 13
6 14
6 16
6 17
7 9
7 10
7 12
7 14
7 16
7 17
8 10
8 11
8 13
8 15
8 16
8 17
9 10
9 11
9 12
9 15
9 17
10 14
10 15
10 16
11 12
11 13
11 16
12 13
12 15
13 14
13 15
13 16
14 16
14 17
15 17
16 17
16
71
0 1
0 2
0 6
0 7
0 10
0 12
0 13
0 14
1 2
1 3
1 5
1 9
1 12
1 13
1 15
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
3 4
3 6
3 7
3 10
4 6
4 7
4 8
4 9
4 10
4 11
5 6
5 7
5 8
5 9
5 10
5 12
5 13
5 14
5 15
6 8
6 10
6 13
7 8
7 9
7 10
7 11
7 13
7 14
7 15
8 9
8 10
8 12
8 13
8 14
9 10
9 14
10 11
10 13
10 14
10 15
11 12
11 13
13 14
13 15
1
0
4
5
0 1
0 2
0 3
1 2
1 3
18
87
0 1
0 2
0 5
0 6
0 8
0 13
0 16
0 17
1 2
1 3
1 4
1 6
1 7
1 8
1 9
1 10
1 11
1 13
1 14
1 15
2 3
2 11
2 14
2 16
3 8
3 9
3 10
3 12
3 16
3 17
4 5
4 8
4 11
4 15
5 6
5 7
5 8
5 9
5 10
5 12
5 13
5 14
5 16
5 17
6 7
6 8
6 9
6 10
6 11
6 13
6 14
6 16
6 17
7 10
7 11
7 13
7 17
8 9
8 10
8 13
8 14
8 15
8 16
8 17
9 11
9 13
9 15
9 16
10 12
10 13
10 14
10 15
10 17
11 12
11 15
11 16
12 13
12 14
12 15
12 16
12 17
13 15
13 16
14 17
15 16
15 17
16 17
1
0
4
6
0 1
0 2
0 3
1 2
1 3
2 3
9
25
0 1
0 2
0 4
0 6
0 7
0 8
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 8
3 4
3 5
3 6
3 7
4 7
4 8
5 7
5 8
6 7
6 8
7 8
13
35
0 1
0 2
0 3
0 4
0 5
0 7
0 9
0 12
1 5
1 6
1 7
1 11
2 5
2 6
2 7
2 8
3 5
3 6
3 7
3 10
4 6
4 10
4 12
5 6
5 9
5 10
5 12
6 10
6 11
6 12
7 8
7 10
7 12
9 12
10 11
18
98
0 1
0 3
0 5
0 6
0 7
0 10
0 12
0 14
0 16
1 2
1 3
1 4
1 5
1 6
1 8
1 9
1 11
1 14
1 15
1 17
2 3
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 13
2 14
2 15
3 4
3 5
3 6
3 7
3 8
3 9
3 12
3 13
3 14
3 15
4 5
4 6
4 7
4 11
4 13
4 15
4 17
5 6
5 7
5 8
5 9
5 11
5 13
5 15
5 16
6 7
6 9
6 10
6 13
6 14
6 15
6 16
7 8
7 12
7 13
7 17
8 10
8 12
8 13
8 14
8 15
8 17
9 10
9 12
9 13
9 16
9 17
10 11
10 12
10 14
10 15
10 17
11 12
11 13
11 14
11 15
11 17
12 13
12 15
12 16
12 17
13 15
13 17
14 16
14 17
15 16
16 17
19
100
0 1
0 2
0 3
0 5
0 6
0 7
0 8
0 9
0 11
0 12
0 14
0 15
0 16
0 17
1 2
1 4
1 7
1 9
1 10
1 11
1 14
1 15
1 16
1 17
1 18
2 3
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 14
2 18
3 4
3 6
3 8
3 9
3 10
3 14
3 16
3 18
4 5
4 6
4 10
4 11
4 12
4 14
4 15
4 16
4 17
5 8
5 10
5 12
5 13
5 14
5 15
5 17
5 18
6 8
6 9
6 10
6 13
6 15
7 9
7 10
7 12
7 15
7 16
8 9
8 11
8 12
8 13
8 14
8 15
8 17
8 18
9 11
9 12
9 13
9 16
9 17
10 12
10 13
10 15
10 18
11 12
11 13
11 15
11 16
11 18
12 14
13 16
13 17
14 15
14 16
15 16
16 17
17 18
12
42
0 1
0 2
0 5
0 6
0 7
0 8
0 9
0 11
1 2
1 3
1 4
1 5
1 6
1 9
1 10
1 11
2 3
2 4
2 6
2 9
2 10
2 11
3 9
3 10
3 11
4 8
4 9
5 7
5 8
5 9
5 11
6 7
6 8
6 9
6 11
7 8
7 9
7 10
7 11
8 10
8 11
10 11
18
79
0 1
0 2
0 5
0 6
0 7
0 8
0 12
0 13
0 15
1 2
1 3
1 4
1 11
1 12
1 14
1 16
1 17
2 3
2 4
2 5
2 8
2 9
2 12
2 14
2 17
3 4
3 6
3 9
3 14
3 16
4 5
4 9
4 12
4 14
4 15
4 17
5 7
5 8
5 11
5 12
5 14
6 9
6 10
6 11
6 12
6 16
6 17
7 9
7 11
7 13
7 14
7 15
7 17
8 9
8 10
8 11
8 13
8 14
8 16
9 13
9 14
9 16
9 17
10 12
10 13
10 14
10 15
10 17
11 15
12 13
12 14
12 15
12 17
13 14
13 16
13 17
14 16
14 17
15 17
18
92
0 1
0 2
0 3
0 4
0 6
0 10
0 12
0 13
0 14
0 15
0 16
0 17
1 3
1 4
1 6
1 7
1 8
1 9
1 14
1 15
1 17
2 3
2 4
2 5
2 6
2 8
2 9
2 10
2 13
2 14
2 15
3 4
3 5
3 6
3 7
3 9
3 10
3 11
3 12
3 13
3 14
3 15
3 17
4 5
4 7
4 8
4 9
4 11
4 12
4 13
4 15
4 16
4 17
5 8
5 10
5 13
5 15
6 8
6 9
6 11
6 13
6 14
6 17
7 9
7 12
7 13
7 14
7 15
7 16
8 9
8 10
8 11
8 12
8 13
8 16
9 11
9 12
9 13
9 14
9 15
10 11
10 13
10 14
10 17
11 17
12 14
12 15
12 16
13 14
13 17
14 15
16 17
9
18
0 1
0 3
0 6
0 7
0 8
1 2
1 3
1 4
2 3
2 4
2 7
2 8
3 4
3 5
3 6
4 5
4 8
6 7
11
36
0 1
0 2
0 3
0 4
0 5
0 7
0 9
0 10
1 2
1 3
1 4
1 5
1 7
1 8
1 9
1 10
2 3
2 5
2 7
2 8
2 9
2 10
3 4
3 6
3 8
4 6
4 8
5 7
5 8
6 7
6 8
6 10
7 9
7 10
8 9
8 10
6
13
0 1
0 2
0 3
0 4
0 5
1 2
1 3
1 4
1 5
2 3
2 4
3 4
3 5
3
2
0 1
1 2
1
0
3
3
0 1
0 2
1 2
19
92
0 1
0 2
0 3
0 4
0 5
0 7
0 11
0 13
0 15
0 17
0 18
1 3
1 4
1 5
1 7
1 10
1 11
1 12
1 14
1 16
1 18
2 6
2 8
2 9
2 13
2 15
2 16
3 4
3 6
3 9
3 10
3 11
3 12
3 14
3 15
3 16
3 17
4 5
4 7
4 8
4 11
4 12
4 14
4 15
5 6
5 7
5 8
5 9
5 12
5 13
5 14
5 18
6 7
6 8
6 9
6 12
6 13
6 14
6 15
6 16
6 17
7 8
7 10
7 11
7 12
7 16
7 17
8 9
8 11
8 12
8 13
8 15
8 17
9 10
9 11
9 17
9 18
10 13
11 13
11 16
12 14
12 18
13 15
13 16
13 17
14 15
14 16
14 17
14 18
15 18
16 17
17 18
20
107
0 1
0 2
0 3
0 5
0 6
0 9
0 10
0 11
0 12
0 13
0 14
0 15
0 16
0 17
0 18
0 19
1 2
1 3
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 15
2 5
2 6
2 8
2 9
2 10
2 11
2 12
3 4
3 5
3 6
3 7
3 11
3 14
3 17
4 5
4 6
4 7
4 8
4 11
4 12
4 13
4 14
4 15
4 16
4 17
4 18
4 19
5 6
5 9
5 10
5 18
5 19
6 8
6 12
6 14
6 15
6 19
7 8
7 10
7 11
7 12
7 13
7 14
7 15
7 18
7 19
8 10
8 11
8 12
8 15
8 17
8 18
9 10
9 12
9 13
9 15
9 17
9 18
10 13
10 15
10 18
10 19
11 12
11 14
11 16
11 17
11 18
12 13
12 17
12 19
13 14
13 16
13 17
13 18
14 18
15 16
15 19
16 17
16 19
3
2
0 1
0 2
17
76
0 1
0 2
0 4
0 5
0 12
0 14
1 2
1 4
1 5
1 8
1 11
1 13
1 16
2 3
2 5
2 6
2 7
2 10
2 14
2 16
3 4
3 8
3 10
3 11
3 12
3 13
3 15
3 16
4 5
4 6
4 9
4 11
4 12
4 13
4 14
4 15
4 16
5 6
5 7
5 8
5 9
5 10
5 12
5 15
5 16
6 7
6 9
6 11
6 12
6 13
6 14
7 8
7 10
7 11
7 12
7 14
7 15
7 16
8 9
8 12
8 13
8 15
8 16
9 11
9 13
10 13
10 14
10 16
11 12
11 13
11 14
11 16
12 13
12 14
14 15
14 16
14
49
0 1
0 2
0 3
0 6
0 9
0 11
0 13
1 2
1 3
1 4
1 5
1 9
1 11
1 13
2 8
2 9
2 10
2 11
2 12
3 5
3 6
3 8
3 9
3 12
4 5
4 7
4 8
4 10
4 11
4 12
4 13
5 6
5 8
5 9
5 12
5 13
6 10
6 12
7 11
7 13
8 9
8 10
8 11
8 12
9 11
9 13
10 12
10 13
12 13
3
3
0 1
0 2
1 2
4
4
0 1
0 2
0 3
1 2
17
72
0 1
0 2
0 5
0 6
0 12
0 13
0 14
0 16
1 3
1 4
1 5
1 10
1 11
1 12
1 13
1 14
1 16
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 14
2 16
3 4
3 5
3 6
3 8
3 9
3 11
3 12
3 13
3 14
4 5
4 6
4 13
4 14
4 15
4 16
5 8
5 10
5 12
5 13
5 14
5 15
5 16
6 8
6 9
6 11
6 16
7 15
8 9
8 10
8 14
8 16
9 11
9 12
9 13
9 15
10 16
11 13
11 14
11 16
12 14
12 15
12 16
13 14
13 16
14 15
15 16
20
99
0 1
0 2
0 3
0 8
0 9
0 12
0 13
0 14
0 16
0 17
0 18
0 19
1 2
1 3
1 4
1 5
1 7
1 13
1 14
1 19
2 8
2 9
2 11
2 12
2 13
2 16
3 4
3 5
3 6
3 8
3 9
3 10
3 13
3 14
4 6
4 8
4 11
4 12
4 14
4 16
4 19
5 7
5 8
5 9
5 10
5 13
5 14
5 15
5 17
5 18
6 8
6 9
6 10
6 12
6 13
6 16
6 19
7 8
7 10
7 12
7 16
7 19
8 9
8 10
8 11
8 12
8 13
8 15
8 17
9 11
9 12
9 15
9 16
9 17
9 18
9 19
10 12
10 14
10 15
11 12
11 13
11 15
11 17
11 18
11 19
12 13
12 15
12 18
12 19
13 15
13 17
13 18
13 19
14 15
14 16
14 17
14 18
15 18
17 19
2
1
0 1
8
14
0 1
0 2
0 3
1 3
1 7
2 4
2 5
2 7
3 4
3 7
4 5
4 6
5 7
6 7
7
14
0 1
0 2
0 3
0 4
0 6
1 3
1 4
1 5
2 3
2 4
2 5
3 4
4 5
4 6
12
39
0 1
0 2
0 3
0 5
0 7
0 8
1 2
1 3
1 4
1 5
1 7
1 9
1 10
2 6
2 8
2 9
2 11
3 5
3 7
3 8
3 9
3 11
4 7
4 9
4 10
4 11
5 6
5 7
5 9
5 10
6 7
6 8
6 10
7 10
8 9
8 10
8 11
9 10
10 11
17
79
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 9
0 10
0 14
0 15
0 16
1 3
1 5
1 7
1 8
1 10
1 11
1 15
2 3
2 4
2 6
2 8
2 16
3 4
3 5
3 6
3 7
3 8
3 9
3 11
3 13
3 15
3 16
4 5
4 6
4 7
4 9
4 13
4 14
4 16
5 6
5 9
5 11
5 12
5 14
5 15
6 7
6 8
6 9
6 10
6 12
6 13
6 15
7 8
7 9
7 10
7 11
7 13
7 15
8 10
8 14
8 15
8 16
9 10
9 11
9 13
9 15
10 11
10 13
11 12
11 13
11 14
11 15
12 13
12 15
12 16
13 15
14 16
9
25
0 1
0 3
0 5
0 6
0 7
1 2
1 5
1 6
1 7
1 8
2 5
2 6
2 7
2 8
3 4
3 5
4 5
4 6
4 7
4 8
5 7
5 8
6 7
6 8
7 8
4
6
0 1
0 2
0 3
1 2
1 3
2 3
9
24
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
1 5
1 7
1 8
2 3
2 5
2 6
2 7
3 4
3 6
3 8
4 5
4 6
4 8
6 7
6 8
7 8
18
82
0 1
0 2
0 3
0 4
0 6
0 7
0 8
0 9
0 11
0 13
0 14
0 15
0 16
1 2
1 3
1 7
1 8
1 13
1 15
1 16
1 17
2 3
2 5
2 7
2 8
2 9
2 10
2 13
2 15
3 5
3 9
3 11
3 12
3 13
3 14
3 15
4 6
4 7
4 8
4 10
4 12
4 13
4 16
5 15
6 7
6 9
6 10
6 14
6 15
6 16
6 17
7 8
7 9
7 10
7 13
7 14
7 16
7 17
8 10
8 11
8 13
8 14
8 16
8 17
9 10
9 12
9 15
10 13
10 14
10 15
11 12
11 14
12 13
12 14
12 15
12 17
13 15
14 16
14 17
15 16
15 17
16 17
9
21
0 1
0 2
0 4
0 5
1 2
1 3
1 4
1 7
2 3
2 4
2 6
2 8
3 6
3 7
4 5
5 6
5 7
5 8
6 7
6 8
7 8
20
112
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 12
0 15
0 17
0 18
0 19
1 2
1 4
1 5
1 7
1 8
1 10
1 13
1 14
1 15
1 16
2 3
2 4
2 7
2 8
2 11
2 13
2 19
3 4
3 5
3 6
3 7
3 9
3 10
3 11
3 13
3 14
3 16
3 17
4 5
4 7
4 8
4 9
4 13
4 15
4 16
4 18
4 19
5 6
5 11
5 12
5 14
5 16
5 17
5 18
6 7
6 8
6 10
6 11
6 12
6 13
6 14
6 15
6 17
6 18
6 19
7 9
7 11
7 12
7 14
7 15
7 18
8 9
8 10
8 11
8 12
8 16
8 19
9 10
9 11
9 14
9 15
9 16
9 18
10 12
10 13
10 15
10 16
10 17
10 18
11 12
11 13
11 14
11 15
11 17
11 18
12 14
12 16
13 15
13 16
13 17
13 19
14 15
14 17
14 18
14 19
15 19
16 18
17 18
17
78
0 1
0 2
0 3
0 4
0 5
0 9
0 12
0 14
0 15
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 6
2 7
2 9
2 10
2 11
2 12
2 15
2 16
3 4
3 7
3 8
3 9
3 12
3 13
3 14
3 15
3 16
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 13
4 14
4 15
5 7
5 15
5 16
6 7
6 8
6 11
6 12
6 13
6 15
6 16
7 10
7 11
7 15
7 16
8 9
8 12
8 14
8 15
9 10
9 12
9 13
9 14
9 15
9 16
10 11
10 14
10 15
10 16
12 16
13 14
13 15
13 16
14 16
3
2
0 1
0 2
15
66
0 1
0 2
0 5
0 7
0 8
0 9
0 10
0 12
0 14
1 2
1 4
1 5
1 6
1 9
1 10
1 11
1 13
1 14
2 3
2 4
2 6
2 7
2 9
2 10
2 11
2 12
2 13
2 14
3 6
3 7
3 8
3 9
3 11
4 7
4 8
4 9
4 10
4 11
4 12
4 13
5 6
5 7
5 9
5 13
5 14
6 7
6 8
6 13
6 14
7 8
7 9
7 10
7 11
7 12
7 13
8 9
8 10
9 11
9 12
9 13
10 11
10 12
11 12
11 14
12 13
13 14
5
8
0 1
0 3
0 4
1 2
1 3
2 3
2 4
3 4
3
2
0 1
1 2
18
83
0 1
0 2
0 4
0 7
0 10
0 12
0 14
0 16
0 17
1 2
1 3
1 4
1 5
1 9
1 10
1 11
1 15
1 16
2 3
2 5
2 6
2 7
2 8
2 9
2 10
2 13
2 14
2 15
2 16
2 17
3 4
3 6
3 9
3 11
3 13
3 14
3 16
3 17
4 9
4 10
4 14
4 16
4 17
5 8
5 9
5 11
5 12
5 16
5 17
6 13
6 14
6 16
6 17
7 8
7 9
7 10
7 11
7 13
7 15
8 10
8 11
8 14
8 16
9 10
9 11
9 12
9 13
9 15
9 16
9 17
10 11
10 12
10 17
11 14
11 16
11 17
12 13
13 14
13 15
14 16
14 17
15 16
16 17
8
14
0 1
0 2
0 3
0 4
0 5
0 6
0 7
1 2
2 3
2 6
3 4
3 5
3 6
6 7
9
25
0 1
0 3
0 6
1 2
1 3
1 4
1 6
1 8
2 3
2 4
2 5
2 6
2 7
2 8
3 4
3 6
3 7
4 5
4 6
4 7
5 6
5 7
6 7
6 8
7 8
12
40
0 1
0 2
0 4
0 5
0 6
0 7
0 8
0 9
0 10
1 2
1 3
1 4
1 6
1 7
1 8
1 9
1 11
2 5
2 10
2 11
3 4
3 7
3 9
3 11
4 5
4 6
4 8
4 10
5 6
5 8
5 9
5 10
5 11
6 7
6 10
7 9
7 11
8 11
9 11
10 11
17
67
0 1
0 2
0 4
0 5
0 7
0 9
0 10
0 11
0 13
1 3
1 4
1 7
1 8
1 9
1 10
1 12
1 13
1 16
2 5
2 6
2 7
2 8
2 11
2 12
2 13
2 14
2 16
3 5
3 8
3 11
3 12
3 16
4 5
4 7
4 8
4 10
4 12
4 13
4 15
4 16
5 6
5 7
5 8
5 9
5 10
5 12
5 16
6 8
6 9
6 11
6 15
7 10
7 11
7 12
7 15
8 9
8 11
9 10
9 15
10 15
10 16
11 12
11 13
12 13
12 15
14 15
15 16
8
18
0 1
0 2
0 3
0 4
0 6
1 4
1 6
1 7
2 3
2 4
2 6
3 5
3 7
4 5
4 6
4 7
5 7
6 7
10
31
0 1
0 2
0 3
0 6
0 8
1 2
1 3
1 4
1 9
2 3
2 4
2 6
2 8
2 9
3 5
3 6
3 7
3 8
3 9
4 6
4 8
4 9
5 7
5 8
5 9
6 7
6 8
6 9
7 8
7 9
8 9
13
47
0 1
0 3
0 4
0 7
0 8
0 10
0 11
1 2
1 4
1 5
1 6
1 7
1 8
1 10
1 11
1 12
2 3
2 6
2 7
2 8
2 9
2 12
3 4
3 5
3 7
3 8
3 9
3 10
3 11
4 5
4 6
4 7
4 9
4 10
4 11
5 6
5 8
6 7
6 8
6 9
6 10
6 11
7 9
7 10
7 12
9 11
10 11
20
116
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 14
0 16
0 17
0 19
1 3
1 5
1 6
1 8
1 9
1 10
1 11
1 13
1 14
1 15
1 16
1 18
2 5
2 6
2 7
2 8
2 9
2 12
2 13
2 16
2 17
2 18
2 19
3 4
3 5
3 7
3 8
3 9
3 11
3 12
3 13
3 14
3 15
3 17
3 18
4 5
4 6
4 12
4 13
4 14
4 16
4 18
5 6
5 7
5 8
5 10
5 13
5 14
5 16
5 17
6 8
6 9
6 10
6 11
6 14
6 16
6 17
6 18
6 19
7 8
7 11
7 12
7 15
7 16
7 17
7 19
8 12
8 15
8 16
8 18
9 11
9 14
9 15
10 11
10 13
10 14
10 17
10 18
11 12
11 14
11 16
11 17
11 19
12 15
12 16
12 19
13 14
13 15
13 17
13 19
14 15
14 16
14 17
15 16
15 18
15 19
16 17
16 18
16 19
17 18
17 19
17
87
0 1
0 2
0 3
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 16
1 2
1 5
1 6
1 8
1 9
1 10
1 11
1 12
1 13
1 15
1 16
2 7
2 8
2 10
2 12
2 16
3 4
3 5
3 7
3 12
3 13
3 15
3 16
4 5
4 6
4 8
4 11
4 16
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
5 16
6 8
6 9
6 12
6 13
6 14
6 15
6 16
7 8
7 10
7 11
7 12
7 13
7 14
7 15
8 9
8 11
8 13
8 14
8 15
8 16
9 11
9 12
9 13
10 12
10 14
10 16
11 12
11 14
11 15
11 16
12 14
12 15
12 16
13 14
13 15
14 16
15 16
15
53
0 1
0 2
0 4
0 5
0 6
0 8
0 13
1 2
1 5
1 6
1 9
1 10
1 11
2 3
2 8
2 12
3 4
3 6
3 9
3 10
3 12
3 13
3 14
4 6
4 7
4 8
4 10
4 11
4 13
5 7
5 9
5 12
5 13
5 14
6 8
6 9
6 10
6 11
6 12
6 14
7 9
7 11
7 12
8 11
8 13
9 11
9 14
10 12
10 13
10 14
12 13
12 14
13 14
3
3
0 1
0 2
1 2
8
17
0 1
0 3
0 7
1 2
1 3
1 5
1 6
1 7
2 3
2 7
3 4
3 5
3 6
4 7
5 6
5 7
6 7
7
12
0 1
0 3
0 4
0 5
0 6
1 2
1 4
2 3
2 5
2 6
3 5
3 6
3
2
0 1
1 2
5
6
0 1
0 3
0 4
1 2
1 4
2 4
11
29
0 1
0 2
0 3
0 4
0 6
0 7
0 9
1 2
1 3
1 5
1 7
1 8
2 5
2 8
2 10
3 5
3 9
4 5
4 6
4 9
4 10
5 9
6 7
6 8
6 9
6 10
7 9
8 9
8 10
4
5
0 1
0 2
0 3
1 3
2 3
1
0
8
18
0 1
0 2
0 4
0 5
0 7
1 2
1 3
1 4
1 6
2 3
2 4
2 6
3 4
3 7
4 6
4 7
5 7
6 7
13
47
0 1
0 2
0 5
0 7
0 12
1 3
1 4
1 6
1 8
1 12
2 3
2 4
2 5
2 6
2 7
2 8
2 12
3 4
3 6
3 7
3 8
3 9
3 10
3 11
3 12
4 5
4 6
4 7
4 8
4 11
4 12
5 7
5 8
5 9
5 11
6 7
6 8
6 9
6 10
6 11
7 11
8 11
8 12
9 12
10 11
10 12
11 12
16
57
0 1
0 2
0 3
0 4
0 8
0 12
1 2
1 4
1 7
1 8
1 11
1 12
1 14
2 4
2 9
2 12
2 14
2 15
3 5
3 8
3 11
3 12
3 13
3 14
4 5
4 10
4 12
4 14
4 15
5 6
5 7
5 9
5 10
5 13
5 14
5 15
6 7
6 8
6 9
6 10
6 11
6 13
6 15
7 10
7 11
7 13
7 15
9 10
9 11
9 13
9 15
10 11
10 12
10 14
11 12
11 13
11 15
8
17
0 1
0 2
0 3
0 5
0 7
1 2
1 5
2 3
2 4
2 5
2 6
3 4
3 5
3 6
3 7
4 6
4 7
9
21
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
1 4
1 8
2 3
2 5
2 7
2 8
3 5
3 6
3 8
4 5
4 8
5 7
6 8
4
4
0 1
0 3
1 2
2 3
8
21
0 1
0 2
0 4
0 5
0 6
1 3
1 5
1 6
1 7
2 3
2 4
2 5
2 7
3 4
3 5
3 7
4 5
4 6
4 7
5 6
6 7
13
42
0 1
0 2
0 3
0 4
0 5
0 6
0 10
1 2
1 4
1 5
1 6
1 8
1 9
1 11
2 4
2 5
2 7
2 8
2 9
2 11
3 6
3 9
3 12
4 5
4 6
4 10
4 11
4 12
5 7
5 9
5 10
5 11
6 7
6 8
6 9
6 11
7 11
8 9
8 11
8 12
9 10
11 12
19
88
0 1
0 2
0 3
0 5
0 6
0 8
0 10
0 12
0 15
0 16
0 17
1 6
1 8
1 9
1 16
1 17
1 18
2 4
2 5
2 6
2 7
2 8
2 10
2 11
2 15
3 4
3 6
3 7
3 8
3 10
3 11
3 13
3 15
3 17
4 7
4 9
4 12
4 13
4 15
4 16
5 6
5 10
5 11
5 12
5 13
5 14
5 15
5 16
5 18
6 7
6 8
6 11
6 12
6 13
6 14
6 15
6 17
7 10
7 11
7 13
7 14
7 17
7 18
8 9
8 13
8 14
8 15
9 10
9 12
9 15
9 16
10 11
10 18
11 15
11 16
11 18
12 15
12 16
12 18
13 14
13 15
13 16
13 18
14 15
14 16
14 18
15 17
15 18
9
22
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
1 2
1 4
1 5
1 6
1 7
2 3
2 4
2 5
2 6
2 7
3 7
4 8
6 7
6 8
8
17
0 1
0 2
0 4
1 5
1 6
2 3
2 4
2 5
2 6
2 7
3 5
4 5
4 6
4 7
5 6
5 7
6 7
20
110
0 1
0 2
0 3
0 4
0 5
0 6
0 8
0 10
0 11
0 12
0 14
0 17
1 2
1 3
1 5
1 7
1 8
1 10
1 11
1 13
1 14
1 15
1 18
2 6
2 7
2 9
2 13
2 16
2 17
3 4
3 5
3 6
3 7
3 8
3 14
3 16
3 17
3 18
3 19
4 5
4 7
4 8
4 10
4 12
4 13
4 17
4 19
5 10
5 11
5 12
5 14
5 15
5 17
5 18
5 19
6 8
6 9
6 10
6 13
6 16
6 17
6 18
6 19
7 8
7 9
7 10
7 12
7 13
7 14
7 15
7 16
7 19
8 9
8 10
8 11
8 13
8 14
8 15
8 16
8 19
9 11
9 12
9 13
9 17
9 19
10 13
10 15
10 16
10 17
10 18
11 14
11 15
11 16
11 17
12 16
12 17
12 18
12 19
13 15
13 16
13 19
14 15
14 18
15 16
15 18
15 19
16 18
16 19
17 19
18 19
16
64
0 1
0 2
0 3
0 4
0 5
0 10
0 11
0 12
0 13
0 14
1 2
1 6
1 8
1 10
1 13
1 15
2 4
2 5
2 9
2 12
3 4
3 5
3 7
3 12
3 14
3 15
4 5
4 6
4 7
4 9
4 10
5 7
5 8
5 9
5 10
5 11
5 12
5 13
5 14
6 7
6 9
6 10
6 11
6 13
6 15
7 8
7 9
7 12
7 13
8 9
8 11
8 12
8 13
8 15
9 11
9 13
9 14
9 15
10 11
10 13
10 14
11 13
11 14
12 14
2
1
0 1
5
9
0 1
0 2
0 4
1 2
1 3
1 4
2 3
2 4
3 4
4
5
0 1
0 3
1 2
1 3
2 3
7
14
0 1
0 2
0 3
0 4
0 6
1 2
1 3
1 5
1 6
2 3
3 4
3 5
3 6
4 6
18
81
0 1
0 2
0 3
0 4
0 6
0 9
0 10
0 11
0 12
0 13
0 16
1 2
1 3
1 5
1 8
1 9
1 10
1 11
1 15
1 17
2 5
2 7
2 8
2 9
2 12
2 13
2 15
2 16
3 4
3 5
3 6
3 7
3 9
3 10
3 11
3 13
3 14
3 15
3 16
4 5
4 8
4 9
4 16
5 8
5 11
5 12
5 13
5 16
5 17
6 7
6 9
6 11
6 12
6 13
6 14
6 16
7 9
7 12
7 14
7 15
8 10
8 12
8 16
9 10
9 17
10 11
10 16
11 12
11 13
11 14
11 15
11 17
12 14
12 16
12 17
13 14
13 15
13 16
13 17
14 15
15 17
11
35
0 1
0 2
0 3
0 5
0 8
1 2
1 3
1 5
1 7
1 8
1 9
1 10
2 3
2 4
2 5
2 7
2 8
2 9
3 4
3 7
3 8
3 10
4 5
4 6
4 7
4 8
5 6
5 7
5 8
5 9
5 10
6 9
6 10
8 9
8 10
13
43
0 1
0 2
0 3
0 4
0 7
0 9
1 3
1 5
1 7
1 8
1 10
2 3
2 4
2 5
2 6
2 9
2 11
2 12
3 5
4 7
4 10
4 11
5 6
5 10
5 12
6 7
6 8
6 9
6 11
7 8
7 9
7 10
7 11
7 12
8 9
8 10
8 11
8 12
9 10
9 11
9 12
10 11
10 12
13
39
0 1
0 2
0 3
0 4
0 5
0 9
0 10
0 12
1 2
1 3
1 5
1 6
1 8
1 9
2 6
2 7
2 8
2 10
3 5
3 6
3 8
3 9
3 10
3 12
4 6
4 7
4 8
4 9
4 11
5 6
5 11
6 7
6 10
7 8
7 10
8 11
8 12
9 10
10 12
15
54
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 9
0 11
0 13
0 14
1 7
1 10
1 11
1 12
2 3
2 4
2 6
2 7
2 12
3 4
3 9
3 13
4 5
4 6
4 7
4 9
4 10
4 11
4 12
5 6
5 8
5 11
5 13
6 7
6 8
6 10
6 11
6 13
7 10
7 11
7 12
8 10
8 11
8 12
9 10
9 11
9 14
10 11
10 12
11 12
11 13
11 14
13 14
0
AC output:

Code: Select all

NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
Check input and AC output for thousands of problems on uDebug!

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

Re: 10004 - Bicoloring

Post by brianfry713 » Wed Oct 08, 2014 8:38 pm

musfiqur.cse and Shihab, try input:

Code: Select all

4
3
0 3
1 2
2 3
0
AC output: BICOLORABLE.
Try using a DFS that visits the nodes in the correct search order, use recursion or a stack.
http://en.wikipedia.org/wiki/Depth-first_search
Check input and AC output for thousands of problems on uDebug!

efrshuvo
New poster
Posts: 4
Joined: Thu Nov 08, 2012 9:25 am

Re: 10004 - Bicoloring

Post by efrshuvo » Mon Nov 03, 2014 1:00 pm

It is really too much frustrating. All sample input output passed ( All posted in this thread) but still WA.

Code: Select all


#include<cstdio>
#include<list>
#include<cstring>

#define MAX_NODE 200
#define MAX_EDGE 10000


using namespace std;

int colored[MAX_NODE];

int dfs(list<int> adj[],int v,int visited[],int color=1,int parent=0)
{
	visited[v]=1;
	colored[v]=!color;
	list<int>::iterator i;
    for(i = adj[v].begin(); i != adj[v].end(); ++i)
	{
        if(!visited[*i])
            return dfs(adj,*i, visited,!color,v);
		else
			if(*i!=parent)
			{
				if(colored[v]==colored[*i])
					return 0;
			}

	}

	return 1;
}

int is_bicolorable(list<int> adj[],int v,int visited[],int n)
{
	for(int i = 0; i < n; i++)
	{
        if(!visited[i])
		{
            if(!dfs(adj, i,visited))
				return 0;
		}
	}
	return 1;
}

int main()
{
	int n,u,v;
	long l;
	list<int> adj[MAX_EDGE];
	int visited[MAX_NODE];
	short bicolored=1;
	//freopen("E:\\acm\\10004_in.txt","r",stdin);
	while(1)
	{
		memset(visited, 0,sizeof(visited));
		memset(colored, -1,sizeof(colored));
		
		scanf("%d",&n);
		if(n<=0)
			break;

	
		scanf("%ld",&l);
		
		for(long i=0;i<l;i++)
		{
			scanf("%d %d",&u,&v);
			adj[u].push_back(v);
			adj[v].push_back(u);
		}
		bicolored=is_bicolorable(adj,0,visited,n);
		if(!bicolored)
			printf("NOT BICOLORABLE.\n");
		else
			printf("BICOLORABLE.\n");
		for(long i=0;i<l;i++)
		{
			adj[i].clear();
		}
	}
	return 0;
}
Thanks.

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

Re: 10004 - Bicoloring

Post by lighted » Mon Nov 03, 2014 2:18 pm

Problem description says
the graph will be strongly connected. That is, there will be at least one path from any node to any other node.
So your function is_bicolorable is unnecessary.

I don't know why you got WA. Maybe judge's input contains invalid input. But if you change line this way you'll get Acc. :)

Code: Select all

bicolored = dfs(adj, 0, visited);
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 100 (10000-10099)”