## 11770 - Lighting Away

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

Moderator: Board moderators

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

### Re: WA in problem 11770

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
Learning poster
Posts: 62
Joined: Sat Nov 21, 2009 10:17 pm

### 11770 - Lighting Away

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

``````
If you have determination, you can do anything you want....

naseef_07cuet
Learning poster
Posts: 62
Joined: Sat Nov 21, 2009 10:17 pm

### Re: 11770 - Lighting Away

finally got it...thanks..
If you have determination, you can do anything you want....

m.shawkey
New poster
Posts: 9
Joined: Tue Jun 11, 2013 2:58 pm

### Re: 11770 - Lighting Away

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11770 - Lighting Away

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.
Last edited by brianfry713 on Thu Dec 12, 2013 11:05 pm, edited 1 time in total.
Check input and AC output for thousands of problems on uDebug!

t.tahasin
New poster
Posts: 38
Joined: Tue May 28, 2013 11:21 pm

### Re: 11770 - Lighting Away

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.

Code: Select all

``````code removed after acc.
``````
Last edited by t.tahasin on Tue Dec 24, 2013 7:04 am, edited 3 times in total.

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

### Re: 11770 - Lighting Away

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
``````
Last edited by brianfry713 on Thu Dec 12, 2013 10:48 pm, edited 1 time in total.
Check input and AC output for thousands of problems on uDebug!

t.tahasin
New poster
Posts: 38
Joined: Tue May 28, 2013 11:21 pm

### Re: 11770 - Lighting Away

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11770 - Lighting Away

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.
Check input and AC output for thousands of problems on uDebug!

t.tahasin
New poster
Posts: 38
Joined: Tue May 28, 2013 11:21 pm

### Re: 11770 - Lighting Away

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.

????????
New poster
Posts: 5
Joined: Mon Nov 11, 2013 7:00 pm

### Re: 11770 - Lighting Away

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;

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

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

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

}
return 0;
}
``````

t.tahasin
New poster
Posts: 38
Joined: Tue May 28, 2013 11:21 pm

### Re: 11770 - Lighting Away

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
New poster
Posts: 15
Joined: Fri Aug 15, 2014 8:06 pm

### Re: 11770 - Lighting Away

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