11770 - Lighting Away

[jurajz]

Hi shaon3343,

11504 is very similar problem to this problem. I solved this problem by submitting solution of 11504

Problem 11504 has two differencies. First difference is in input, in 11504 there can be maximum of 100000 vertices, not only 10000. Maximum number of edges is the same. Second difference is in output, in 11504 only one single number is need to output for each test case, in this problem, output has prefix "Case: "

[naseef_07cuet]

Getting WA..Though its works for i/o of previous post.Please anyone help..Here is my code-

Code: Select all

#include<iostream>
#include<vector>
#include<stdio.h>
#include<queue>
#define max 10010

using namespace std;

vector <long> edge[max];

long color[max],node[max],num,indeg[max],visited[max];

void tsort(long n)
{
 queue <long> que;
     for(long j=1;j<=n;j++)
     {
      if(indeg[j]==0)
      {
       que.push(j);
      }
     }
     while(!que.empty())
     {
      long u=que.front();
      //cout<<" "<<u<<" "; 
      node[num]=que.front();
      num++;
      que.pop();
      for(long j=0;j<edge[u].size();j++)
      {
       indeg[edge[u][j]]--;
       if(indeg[edge[u][j]]==0)
       {
        que.push(edge[u][j]);
       }
      }
     }
}

void bfs(long source,long n)
{
     long i;
 for(i=1;i<=n;i++)
 {
  color[i]=1;
 }
 color[source]=2;
 queue <long> q;
 q.push(source);
 while(!q.empty())
 {
  long u=q.front();
   visited[u]=1;
  //cout<<u<<"- ";
  q.pop();
  for(i=0;i<edge[u].size();i++)
  {
    if(color[edge[u][i]]==1)
    {
     color[edge[u][i]]=2;
     q.push(edge[u][i]);
     visited[edge[u][i]]=1;
    }
  }
 }
}

int main()
{
 long t,from,to,n,m,i,j,k,res,cas=1;
 
 cin>>t;
 for(i=0;i<t;i++)
 {
  cin>>n>>m;
  res=0;
  for(j=1;j<=n;j++) {
                    indeg[j]=0;
                    visited[j]=0;
                    }
  for(j=0;j<m;j++)
  {
   cin>>from>>to;
   indeg[to]++;
   edge[from].push_back(to);
   //edge[to].push_back(from);
  }
  num=0;
  tsort(n);
  for(j=0;j<num;j++)
  {
   //cout<<node[j]<<" ";
   if(visited[node[j]]==0)
   {
    bfs(node[j],n);
    res++;
   }
  }
  for(j=1;j<=n;j++)
  {
   if(indeg[j]!=0 && visited[j]==0)
   {
    res++;
    visited[j]=1;
    bfs(j,n);
   }
  }
  printf("Case %ld: %ld\n",cas,res);
  cas++;
  for(j=1;j<=n;j++) 
  {
                    edge[j].clear();
  }
 }
 return 0;
}

[naseef_07cuet]

finally got it...thanks..

[m.shawkey]

Getting WA, any help?

Code: Select all

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

vector <vector <int> > mat;
vector <int> par,num,low;


int next;
void tarjan(int,int);

int main()
{
    int t,m,n;
    int t1,t2,z=0;
    map <int,int> mp; 
    vector <vector <int> > mat1;
    scanf("%d",&t);
    while(z++<t)
    {
        scanf("%d%d",&n,&m);
        mat.clear();
        mat.resize(n);
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&t1,&t2);
            mat[--t1].push_back(--t2);
        }
        par.resize(n); low.resize(n);
        num.resize(n);
        for(int i=0;i<n;i++)
        {
            par[i]=-1;
        }
        next=0;
        for(int i=0;i<n;i++)
        {
            if(par[i]==-1)
            {
                par[i]=i;
                tarjan(i,next);
            }
        }
        mp.clear();
        for(int i=0;i<n;i++)
        {
            if(mp.find(low[i])==mp.end())
            {
                t1=mp.size();
                mp[low[i]]=t1;
            }
        }
        mat1.clear();
        mat1.resize(mp.size());
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<mat[i].size();j++)
            {
                if(low[i]==low[mat[i][j]]) continue;
                mat1[mp[low[mat[i][j]]]].push_back(mp[low[i]]);
            }
        }
        t1=0;
        for(int i=0;i<mat1.size();i++)
        {
            if(mat1[i].size()==0) t1++;
        }
        printf("Case %d: %d\n",z,t1);
    }
    
    return 0;
}


void tarjan(int u,int x)
{
    int v;
    low[u]=num[u]=next++;
    for(int i=0;i<mat[u].size();i++)
    {
        v=mat[u][i];
        if(par[v]==-1)
        {
            par[v]=u;
            tarjan(v,x);
            low[u]=min(low[v],low[u]);
        }
        else if(num[v]>=x) low[u]=min(low[u],num[v]);
    }
}

[brianfry713]

I got AC by running dfs from all nodes with in degree zero and then running dfs from unvisited nodes in decreasing order of their out degree. However, that algorithm would fail on certain test cases like this one, which are not included in the judge's input:

Code: Select all

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

The correct output should be 1, starting at node 1, however my code prints 2, starting at node 2 and then node 1.

[t.tahasin]

WA... I used the strongly connected component algorithm to solve this problem.
I checked with all the inputs in this thread and found OK for all the inputs. Please help.
Thanks in advanced.

Code: Select all

code removed after acc.

[brianfry713]

Input:

Code: Select all

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

4 8
1 2
1 3
1 4
2 3
2 4
3 4
4 1
4 2

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

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

6 16
1 3
1 5
1 6
2 3
2 6
3 2
3 4
3 5
4 2
4 3
4 5
5 1
5 3
5 4
6 2
6 5

4 4
1 4
2 3
2 4
4 3

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

6 17
1 2
1 3
1 4
2 4
2 5
2 6
3 4
3 5
3 6
4 2
4 3
5 1
5 2
5 4
6 3
6 4
6 5

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

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

3 2
1 2
2 1

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

9 40
1 4
1 5
1 7
1 8
2 4
2 5
2 6
2 8
2 9
3 2
3 5
3 9
4 1
4 5
4 9
5 7
5 8
6 2
6 3
6 5
6 7
6 9
7 1
7 3
7 4
7 6
7 8
7 9
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 9
9 2
9 5
9 7
9 8

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

4 6
1 2
1 3
2 3
3 1
3 4
4 1

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

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

9 33
1 2
1 3
1 4
2 3
2 4
2 5
2 7
2 9
3 6
4 1
4 2
4 5
4 6
4 8
5 2
5 4
5 8
5 9
6 8
7 1
7 2
7 3
7 4
7 5
7 9
8 1
8 2
8 4
8 5
8 9
9 2
9 5
9 8

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

9 45
1 3
1 4
1 6
1 7
2 1
2 4
2 5
2 7
2 9
3 1
3 4
3 5
3 9
4 1
4 2
4 3
4 6
4 7
4 9
5 2
5 6
5 7
6 1
6 2
6 4
6 7
6 8
6 9
7 1
7 3
7 4
7 5
7 6
7 8
7 9
8 1
8 3
8 4
8 5
8 6
8 7
8 9
9 3
9 7
9 8

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

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

1 0

2 1
2 1

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

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

5 10
1 2
1 4
1 5
2 1
2 5
3 4
3 5
4 2
5 1
5 4

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

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

2 1
1 2

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

1 0

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

7 19
1 3
1 4
1 7
2 3
2 4
2 5
2 6
2 7
3 1
3 6
4 2
4 3
4 6
4 7
5 2
5 3
5 4
6 7
7 1

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

9 30
1 2
1 3
1 7
1 9
2 4
2 5
2 6
2 9
3 2
3 4
3 7
3 9
4 1
4 5
4 8
5 4
5 6
5 8
6 1
6 8
6 9
7 2
7 8
7 9
8 9
9 1
9 4
9 5
9 7
9 8

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

9 39
1 4
1 6
1 8
1 9
2 1
2 3
2 5
2 6
2 8
3 2
3 4
3 6
3 7
3 9
4 2
4 3
4 5
4 6
4 9
5 1
6 1
6 3
6 4
7 1
7 2
7 5
7 8
7 9
8 2
8 3
8 4
8 6
8 7
8 9
9 2
9 3
9 6
9 7
9 8

2 1
2 1

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

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

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

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

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

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

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

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

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

3 3
1 2
2 3
3 2

7 22
1 2
1 3
1 6
1 7
2 3
2 6
3 4
3 5
4 1
4 6
4 7
5 2
5 3
5 4
5 6
5 7
6 1
6 3
6 4
6 5
6 7
7 1

6 17
1 2
1 6
2 1
2 3
2 4
2 5
3 4
3 5
4 2
4 3
4 6
5 1
5 3
5 4
6 2
6 4
6 5

3 4
1 2
1 3
2 1
3 1

2 2
1 2
2 1

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

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

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

7 20
1 2
1 3
2 5
2 7
3 4
3 5
3 7
4 1
4 3
4 7
5 1
5 3
5 4
5 7
6 3
7 1
7 2
7 4
7 5
7 6

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

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

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

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

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

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

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

6 14
1 6
2 1
2 3
2 5
3 1
3 2
3 4
3 5
3 6
5 1
5 3
5 6
6 1
6 3

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

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

5 8
1 2
1 4
1 5
2 4
4 2
4 3
5 3
5 4

1 0

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

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

3 5
1 2
1 3
2 1
2 3
3 1

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

6 19
1 2
1 4
2 1
2 3
2 4
2 6
3 1
3 2
4 1
4 2
4 3
4 5
4 6
5 3
5 6
6 1
6 2
6 3
6 5

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

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

7 20
1 4
1 7
2 1
2 4
2 6
2 7
3 1
3 6
3 7
4 1
5 2
5 3
5 4
5 6
6 2
6 4
6 7
7 2
7 4
7 5

2 0

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

3 3
1 2
2 1
3 2

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

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

4 4
1 2
1 3
1 4
2 1

3 4
1 2
1 3
2 1
2 3

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

3 1
1 2

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

9 42
1 3
1 5
1 8
2 3
2 4
2 6
2 8
2 9
3 5
3 6
3 8
3 9
4 1
4 2
4 3
4 5
4 6
4 8
5 2
5 3
5 4
5 6
5 8
6 1
6 2
6 3
6 5
6 7
6 8
7 3
7 4
7 5
7 6
8 2
8 3
8 4
8 5
9 3
9 5
9 6
9 7
9 8

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

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

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

2 1
1 2

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

2 1
2 1

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

5 9
1 4
1 5
2 5
3 2
3 4
3 5
4 1
4 2
4 5

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

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

7 16
1 4
1 5
2 1
3 2
3 4
3 5
3 7
4 1
4 5
4 6
6 1
7 1
7 2
7 3
7 4
7 6

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

AC output:

Code: Select all

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

[t.tahasin]

Again WA
Thank you very much brianfry713 for your I/O. I found my mistake. although I could not get my code accepted yet.
I think 2 of your output cases are not correct. Actually I also checked with UVA Toolkit. I have the same output as yours except those two cases.
I think the outputs for Case 83 and Case 84 both should be '1', while your outputs showing '2'.
Can you please check those outputs once again.(Sorry for bothering you).
Thank you again.

[brianfry713]

I corrected the I/O in my previous post.

Try input:

Code: Select all

1
5 8
1 4
1 5
2 4
2 5
3 4
4 3
4 5
5 3

Output should be 2, nodes 1 and 2 have in degree 0.

[t.tahasin]

Thanks a lot brianfry713 after a lot of WA finally I got accepted, but without finding strongly connected components, rather I used most likely a topological ordering.

[????????]

i've tested all the inputs that brianfry713 posted here and i've found no mistake..
i ran dfs in increasing order of indegree ..but i got wa again and again..
someone pls help

Code: Select all

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define pb push_back
#define loop(i,a,b) for(int i=a;i<=b;i++)
#define valid(x,y) x>=1&&x<=6&&y>=1&&y<=6

using namespace std;
typedef long long       lli;
typedef vector<int>     vi;
typedef pair<int,int>   pi;
typedef vector<pi>      vii;
typedef map<string,int> msi;
typedef map<int,int>    mii;
typedef set<int>        si;
typedef queue<int>      qi;
typedef stack<int>      sti;

#define TRvi(c,it)\
    for (vi::iterator it=(c).begin();it!=(c).end();it++)
#define TRvii(c,it)\
    for (vii::iterator it=(c).begin();it!=(c).end();it++)

#define set_zero(a) memset(a,0,sizeof(a))

#define in_i(a) scanf("%d",&a)
#define in_lli(a) scanf("%lld",&a)
#define in_dbl(a) scanf("%lf",&a)
#define in_str(a) scanf("%s",&a)

#define maxm 10005
int color[maxm],press_numb;
vi AdjList[maxm];

void dfs_visit(int u)
{
    color[u]=1;

    TRvi(AdjList[u],v)
        if (!color[*v]) dfs_visit(*v);
}

struct node
{
    int u,w;
    node(int a,int b)
    {
        u=a; w=b;
    }
    bool operator < (const node& p) const {return w>p.w;}
};

int main()
{
    int t,light_numb,line_numb,i,j,k;
    in_i(t); int casee=1;

    while (t--)
    {
        in_i(light_numb); in_i(line_numb);
        int indegree[light_numb+2];

        int u,v;
        set_zero(indegree);


        while(line_numb--)
        {
            in_i(u); in_i(v);

            AdjList[u].pb(v);
            indegree[v]++;
        }
        priority_queue< node > q;

        set_zero(color);
        press_numb=0;

        loop(l,1,light_numb)
            q.push(node(l,indegree[l]));


        while(!q.empty())
        {
            node top=q.top(); q.pop();

            if (!color[top.u]) {press_numb++;dfs_visit(top.u);}
        }

        printf("Case %d: %d\n",casee++,press_numb);

        loop(l,1,light_numb) AdjList[l].clear();
    }
    return 0;
}

[t.tahasin]

hi ????????
try this-
input

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

output

Case 1: 1

while your program output is

Case 1: 2

[sreka11]

Nevermind, I got Acc by doing a topological sort and then a dfs to count the nr of components.