Page 2 of 2
Re: WA in problem 11770
Posted: Sat Apr 03, 2010 10:49 pm
by 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: "
11770 - Lighting Away
Posted: Thu Apr 22, 2010 9:58 am
by 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;
}
Re: 11770 - Lighting Away
Posted: Wed Dec 01, 2010 12:54 pm
by naseef_07cuet
finally got it...thanks..
Re: 11770 - Lighting Away
Posted: Thu Aug 22, 2013 4:45 pm
by 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]);
}
}
Re: 11770 - Lighting Away
Posted: Fri Aug 23, 2013 12:36 am
by 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:
The correct output should be 1, starting at node 1, however my code prints 2, starting at node 2 and then node 1.
Re: 11770 - Lighting Away
Posted: Wed Dec 11, 2013 7:51 am
by 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.
Re: 11770 - Lighting Away
Posted: Wed Dec 11, 2013 11:15 pm
by 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
Re: 11770 - Lighting Away
Posted: Thu Dec 12, 2013 1:51 pm
by 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.
Re: 11770 - Lighting Away
Posted: Thu Dec 12, 2013 11:00 pm
by 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.
Re: 11770 - Lighting Away
Posted: Tue Dec 24, 2013 7:02 am
by 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.
Re: 11770 - Lighting Away
Posted: Mon Jan 06, 2014 2:26 pm
by ????????
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;
}
Re: 11770 - Lighting Away
Posted: Sat Jan 11, 2014 10:12 am
by 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
Re: 11770 - Lighting Away
Posted: Thu Sep 18, 2014 12:05 am
by sreka11
Nevermind, I got Acc by doing a topological sort and then a dfs to count the nr of components.