#include<iostream> #include<vector> #include<cstring> #include<algorithm> #include<unordered_set> using namespace std; vector<int> edge[200005]; int anc[20][200005]; // parent node int level[200005], sbtr[200005]; // depth node dan jumlah node pada subtree int in[200005], out[200005]; // buat cek subtree int visited[200005], revcutter; int powerofTwo[21]; unordered_set<int> cutter; // cutter untuk menandai subtree yang membatasi jawaban, revcutter untuk menandai subtree yang int lg = 18, timer, ans_dist, ans; void dfs(int now, int par){ anc[0][now] = par; level[now] = level[par]+1; visited[now] = 1; in[now] = timer++; for(int dst : edge[now]) if(dst != par) dfs(dst, now); out[now] = timer++; } int last_dfs(int now, int par){ int x = 1; for(int dst : edge[now]) if(dst != par && !cutter.count(dst) && (anc[0][revcutter] != dst)) x += last_dfs(dst, now); return x; } void addEdge(int src, int dst){ edge[src].emplace_back(dst); edge[dst].emplace_back(src); } int lca(int x, int y){ if(level[x] < level[y]) swap(x,y); for(int i = lg; i >= 0; i--) if((level[x] - (1 << i)) >= level[y]) x = anc[i][x]; if(x == y) return x; for(int i = lg; i>=0; i--){ if(anc[i][x] != anc[i][y]){ x = anc[i][x]; y = anc[i][y]; } } return anc[0][x]; } int distance(int x, int y){ return level[x] + level[y] - 2 * level[lca(x,y)]; } // is y subtree of x bool isSubtree(int x, int y){ return (in[x] <= in[y] && out[x] >= out[y]); } int solve(int x, int y){ if(anc[18][x] != anc[18][y]) return 0; int anc_depth = level[lca(x,y)]; int dist_x = level[x] - anc_depth, dist_y = level[y] - anc_depth; int dist = dist_x + dist_y; int to_root = dist + ans_dist; int mid = to_root >> 1, node; if(to_root % 2){ return 0; } for(auto element: cutter){ if(isSubtree(element, y)){ if(dist == ans_dist) return x; return 0; } } if(revcutter && !isSubtree(revcutter, y)){ if(dist == ans_dist) return x; return 0; } if(dist == ans_dist){ if(isSubtree(x,y)){ if(ans_dist){ node = y; for(int i = lg; i >= 0; i--) if((ans_dist - 1) & powerofTwo[i]) node = anc[i][node]; cutter.insert(node); } } else revcutter = x; return x; } cutter.clear(); revcutter = 0; if(dist_y > mid){ node = y; for(int i=lg; i>=0; i--){ if((mid-1) & powerofTwo[i]) { node = anc[i][node]; } } cutter.insert(node); revcutter = anc[0][node]; } else if(dist_y == mid){ node = y; for(int i=lg; i>=0; i--){ if((mid-1) & powerofTwo[i]) { node = anc[i][node]; } } cutter.insert(node); node = x; for(int i=lg; i>=0; i--){ if((mid-1-ans_dist) & powerofTwo[i]) { node = anc[i][node]; } } cutter.insert(node); } else{ node = x; for(int i=lg; i>=0; i--){ if((mid-1-ans_dist) & powerofTwo[i]) { node = anc[i][node]; } } cutter.insert(node); revcutter = anc[0][node]; } ans_dist = mid; return anc[0][node]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); anc[0][0] = 0; int n; cin >> n; // while((1 << lg) < n) // lg++; int u,v,k; for(int i=0;i<n-1;i++) { cin >> u >> v >> k; if(k) addEdge(u, v); } // binary lifting preprocessing memset(visited, 0, sizeof(visited)); for(int i=1; i<=n; i++){ if(!visited[i]) dfs(i,i); } powerofTwo[0]=1; for(int i=1;i<=lg;i++){ powerofTwo[i] = powerofTwo[i-1] << 1; for(int j=1;j<=n;j++){ anc[i][j] = anc[i-1][anc[i-1][j]]; } } int q; cin >> q; int center; // jumlah node yang memenuhi dan tumpuan penghitungan node yang memenuhi while(q--){ revcutter = 0, ans_dist = 0; cutter.clear(); int peeps,x; cin >> peeps; cin >> center; for(int i=0;i<(peeps-1);i++){ cin >> x; // cout << center << endl; if(!center){ continue; } center = solve(center, x); } if(center){ cout << last_dfs(center, center) << '\n'; } else cout << "0\n"; } return 0; }
10 1 2 1 1 3 1 3 7 1 2 4 1 2 6 1 2 5 1 5 9 1 5 10 1 4 8 1 1013 2 1 2 3 1 2 3 4 1 2 3 4 5 1 2 3 4 5 6 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 9 1 2 3 4 5 6 7 8 10 8 1 2 3 4 5 6 7 9 9 1 2 3 4 5 6 7 9 10 8 1 2 3 4 5 6 7 10 7 1 2 3 4 5 6 8 8 1 2 3 4 5 6 8 9 9 1 2 3 4 5 6 8 9 10 8 1 2 3 4 5 6 8 10 7 1 2 3 4 5 6 9 8 1 2 3 4 5 6 9 10 7 1 2 3 4 5 6 10 6 1 2 3 4 5 7 7 1 2 3 4 5 7 8 8 1 2 3 4 5 7 8 9 9 1 2 3 4 5 7 8 9 10 8 1 2 3 4 5 7 8 10 7 1 2 3 4 5 7 9 8 1 2 3 4 5 7 9 10 7 1 2 3 4 5 7 10 6 1 2 3 4 5 8 7 1 2 3 4 5 8 9 8 1 2 3 4 5 8 9 10 7 1 2 3 4 5 8 10 6 1 2 3 4 5 9 7 1 2 3 4 5 9 10 6 1 2 3 4 5 10 5 1 2 3 4 6 6 1 2 3 4 6 7 7 1 2 3 4 6 7 8 8 1 2 3 4 6 7 8 9 9 1 2 3 4 6 7 8 9 10 8 1 2 3 4 6 7 8 10 7 1 2 3 4 6 7 9 8 1 2 3 4 6 7 9 10 7 1 2 3 4 6 7 10 6 1 2 3 4 6 8 7 1 2 3 4 6 8 9 8 1 2 3 4 6 8 9 10 7 1 2 3 4 6 8 10 6 1 2 3 4 6 9 7 1 2 3 4 6 9 10 6 1 2 3 4 6 10 5 1 2 3 4 7 6 1 2 3 4 7 8 7 1 2 3 4 7 8 9 8 1 2 3 4 7 8 9 10 7 1 2 3 4 7 8 10 6 1 2 3 4 7 9 7 1 2 3 4 7 9 10 6 1 2 3 4 7 10 5 1 2 3 4 8 6 1 2 3 4 8 9 7 1 2 3 4 8 9 10 6 1 2 3 4 8 10 5 1 2 3 4 9 6 1 2 3 4 9 10 5 1 2 3 4 10 4 1 2 3 5 5 1 2 3 5 6 6 1 2 3 5 6 7 7 1 2 3 5 6 7 8 8 1 2 3 5 6 7 8 9 9 1 2 3 5 6 7 8 9 10 8 1 2 3 5 6 7 8 10 7 1 2 3 5 6 7 9 8 1 2 3 5 6 7 9 10 7 1 2 3 5 6 7 10 6 1 2 3 5 6 8 7 1 2 3 5 6 8 9 8 1 2 3 5 6 8 9 10 7 1 2 3 5 6 8 10 6 1 2 3 5 6 9 7 1 2 3 5 6 9 10 6 1 2 3 5 6 10 5 1 2 3 5 7 6 1 2 3 5 7 8 7 1 2 3 5 7 8 9 8 1 2 3 5 7 8 9 10 7 1 2 3 5 7 8 10 6 1 2 3 5 7 9 7 1 2 3 5 7 9 10 6 1 2 3 5 7 10 5 1 2 3 5 8 6 1 2 3 5 8 9 7 1 2 3 5 8 9 10 6 1 2 3 5 8 10 5 1 2 3 5 9 6 1 2 3 5 9 10 5 1 2 3 5 10 4 1 2 3 6 5 1 2 3 6 7 6 1 2 3 6 7 8 7 1 2 3 6 7 8 9 8 1 2 3 6 7 8 9 10 7 1 2 3 6 7 8 10 6 1 2 3 6 7 9 7 1 2 3 6 7 9 10 6 1 2 3 6 7 10 5 1 2 3 6 8 6 1 2 3 6 8 9 7 1 2 3 6 8 9 10 6 1 2 3 6 8 10 5 1 2 3 6 9 6 1 2 3 6 9 10 5 1 2 3 6 10 4 1 2 3 7 5 1 2 3 7 8 6 1 2 3 7 8 9 7 1 2 3 7 8 9 10 6 1 2 3 7 8 10 5 1 2 3 7 9 6 1 2 3 7 9 10 5 1 2 3 7 10 4 1 2 3 8 5 1 2 3 8 9 6 1 2 3 8 9 10 5 1 2 3 8 10 4 1 2 3 9 5 1 2 3 9 10 4 1 2 3 10 3 1 2 4 4 1 2 4 5 5 1 2 4 5 6 6 1 2 4 5 6 7 7 1 2 4 5 6 7 8 8 1 2 4 5 6 7 8 9 9 1 2 4 5 6 7 8 9 10 8 1 2 4 5 6 7 8 10 7 1 2 4 5 6 7 9 8 1 2 4 5 6 7 9 10 7 1 2 4 5 6 7 10 6 1 2 4 5 6 8 7 1 2 4 5 6 8 9 8 1 2 4 5 6 8 9 10 7 1 2 4 5 6 8 10 6 1 2 4 5 6 9 7 1 2 4 5 6 9 10 6 1 2 4 5 6 10 5 1 2 4 5 7 6 1 2 4 5 7 8 7 1 2 4 5 7 8 9 8 1 2 4 5 7 8 9 10 7 1 2 4 5 7 8 10 6 1 2 4 5 7 9 7 1 2 4 5 7 9 10 6 1 2 4 5 7 10 5 1 2 4 5 8 6 1 2 4 5 8 9 7 1 2 4 5 8 9 10 6 1 2 4 5 8 10 5 1 2 4 5 9 6 1 2 4 5 9 10 5 1 2 4 5 10 4 1 2 4 6 5 1 2 4 6 7 6 1 2 4 6 7 8 7 1 2 4 6 7 8 9 8 1 2 4 6 7 8 9 10 7 1 2 4 6 7 8 10 6 1 2 4 6 7 9 7 1 2 4 6 7 9 10 6 1 2 4 6 7 10 5 1 2 4 6 8 6 1 2 4 6 8 9 7 1 2 4 6 8 9 10 6 1 2 4 6 8 10 5 1 2 4 6 9 6 1 2 4 6 9 10 5 1 2 4 6 10 4 1 2 4 7 5 1 2 4 7 8 6 1 2 4 7 8 9 7 1 2 4 7 8 9 10 6 1 2 4 7 8 10 5 1 2 4 7 9 6 1 2 4 7 9 10 5 1 2 4 7 10 4 1 2 4 8 5 1 2 4 8 9 6 1 2 4 8 9 10 5 1 2 4 8 10 4 1 2 4 9 5 1 2 4 9 10 4 1 2 4 10 3 1 2 5 4 1 2 5 6 5 1 2 5 6 7 6 1 2 5 6 7 8 7 1 2 5 6 7 8 9 8 1 2 5 6 7 8 9 10 7 1 2 5 6 7 8 10 6 1 2 5 6 7 9 7 1 2 5 6 7 9 10 6 1 2 5 6 7 10 5 1 2 5 6 8 6 1 2 5 6 8 9 7 1 2 5 6 8 9 10 6 1 2 5 6 8 10 5 1 2 5 6 9 6 1 2 5 6 9 10 5 1 2 5 6 10 4 1 2 5 7 5 1 2 5 7 8 6 1 2 5 7 8 9 7 1 2 5 7 8 9 10 6 1 2 5 7 8 10 5 1 2 5 7 9 6 1 2 5 7 9 10 5 1 2 5 7 10 4 1 2 5 8 5 1 2 5 8 9 6 1 2 5 8 9 10 5 1 2 5 8 10 4 1 2 5 9 5 1 2 5 9 10 4 1 2 5 10 3 1 2 6 4 1 2 6 7 5 1 2 6 7 8 6 1 2 6 7 8 9 7 1 2 6 7 8 9 10 6 1 2 6 7 8 10 5 1 2 6 7 9 6 1 2 6 7 9 10 5 1 2 6 7 10 4 1 2 6 8 5 1 2 6 8 9 6 1 2 6 8 9 10 5 1 2 6 8 10 4 1 2 6 9 5 1 2 6 9 10 4 1 2 6 10 3 1 2 7 4 1 2 7 8 5 1 2 7 8 9 6 1 2 7 8 9 10 5 1 2 7 8 10 4 1 2 7 9 5 1 2 7 9 10 4 1 2 7 10 3 1 2 8 4 1 2 8 9 5 1 2 8 9 10 4 1 2 8 10 3 1 2 9 4 1 2 9 10 3 1 2 10 2 1 3 3 1 3 4 4 1 3 4 5 5 1 3 4 5 6 6 1 3 4 5 6 7 7 1 3 4 5 6 7 8 8 1 3 4 5 6 7 8 9 9 1 3 4 5 6 7 8 9 10 8 1 3 4 5 6 7 8 10 7 1 3 4 5 6 7 9 8 1 3 4 5 6 7 9 10 7 1 3 4 5 6 7 10 6 1 3 4 5 6 8 7 1 3 4 5 6 8 9 8 1 3 4 5 6 8 9 10 7 1 3 4 5 6 8 10 6 1 3 4 5 6 9 7 1 3 4 5 6 9 10 6 1 3 4 5 6 10 5 1 3 4 5 7 6 1 3 4 5 7 8 7 1 3 4 5 7 8 9 8 1 3 4 5 7 8 9 10 7 1 3 4 5 7 8 10 6 1 3 4 5 7 9 7 1 3 4 5 7 9 10 6 1 3 4 5 7 10 5 1 3 4 5 8 6 1 3 4 5 8 9 7 1 3 4 5 8 9 10 6 1 3 4 5 8 10 5 1 3 4 5 9 6 1 3 4 5 9 10 5 1 3 4 5 10 4 1 3 4 6 5 1 3 4 6 7 6 1 3 4 6 7 8 7 1 3 4 6 7 8 9 8 1 3 4 6 7 8 9 10 7 1 3 4 6 7 8 10 6 1 3 4 6 7 9 7 1 3 4 6 7 9 10 6 1 3 4 6 7 10 5 1 3 4 6 8 6 1 3 4 6 8 9 7 1 3 4 6 8 9 10 6 1 3 4 6 8 10 5 1 3 4 6 9 6 1 3 4 6 9 10 5 1 3 4 6 10 4 1 3 4 7 5 1 3 4 7 8 6 1 3 4 7 8 9 7 1 3 4 7 8 9 10 6 1 3 4 7 8 10 5 1 3 4 7 9 6 1 3 4 7 9 10 5 1 3 4 7 10 4 1 3 4 8 5 1 3 4 8 9 6 1 3 4 8 9 10 5 1 3 4 8 10 4 1 3 4 9 5 1 3 4 9 10 4 1 3 4 10 3 1 3 5 4 1 3 5 6 5 1 3 5 6 7 6 1 3 5 6 7 8 7 1 3 5 6 7 8 9 8 1 3 5 6 7 8 9 10 7 1 3 5 6 7 8 10 6 1 3 5 6 7 9 7 1 3 5 6 7 9 10 6 1 3 5 6 7 10 5 1 3 5 6 8 6 1 3 5 6 8 9 7 1 3 5 6 8 9 10 6 1 3 5 6 8 10 5 1 3 5 6 9 6 1 3 5 6 9 10 5 1 3 5 6 10 4 1 3 5 7 5 1 3 5 7 8 6 1 3 5 7 8 9 7 1 3 5 7 8 9 10 6 1 3 5 7 8 10 5 1 3 5 7 9 6 1 3 5 7 9 10 5 1 3 5 7 10 4 1 3 5 8 5 1 3 5 8 9 6 1 3 5 8 9 10 5 1 3 5 8 10 4 1 3 5 9 5 1 3 5 9 10 4 1 3 5 10 3 1 3 6 4 1 3 6 7 5 1 3 6 7 8 6 1 3 6 7 8 9 7 1 3 6 7 8 9 10 6 1 3 6 7 8 10 5 1 3 6 7 9 6 1 3 6 7 9 10 5 1 3 6 7 10 4 1 3 6 8 5 1 3 6 8 9 6 1 3 6 8 9 10 5 1 3 6 8 10 4 1 3 6 9 5 1 3 6 9 10 4 1 3 6 10 3 1 3 7 4 1 3 7 8 5 1 3 7 8 9 6 1 3 7 8 9 10 5 1 3 7 8 10 4 1 3 7 9 5 1 3 7 9 10 4 1 3 7 10 3 1 3 8 4 1 3 8 9 5 1 3 8 9 10 4 1 3 8 10 3 1 3 9 4 1 3 9 10 3 1 3 10 2 1 4 3 1 4 5 4 1 4 5 6 5 1 4 5 6 7 6 1 4 5 6 7 8 7 1 4 5 6 7 8 9 8 1 4 5 6 7 8 9 10 7 1 4 5 6 7 8 10 6 1 4 5 6 7 9 7 1 4 5 6 7 9 10 6 1 4 5 6 7 10 5 1 4 5 6 8 6 1 4 5 6 8 9 7 1 4 5 6 8 9 10 6 1 4 5 6 8 10 5 1 4 5 6 9 6 1 4 5 6 9 10 5 1 4 5 6 10 4 1 4 5 7 5 1 4 5 7 8 6 1 4 5 7 8 9 7 1 4 5 7 8 9 10 6 1 4 5 7 8 10 5 1 4 5 7 9 6 1 4 5 7 9 10 5 1 4 5 7 10 4 1 4 5 8 5 1 4 5 8 9 6 1 4 5 8 9 10 5 1 4 5 8 10 4 1 4 5 9 5 1 4 5 9 10 4 1 4 5 10 3 1 4 6 4 1 4 6 7 5 1 4 6 7 8 6 1 4 6 7 8 9 7 1 4 6 7 8 9 10 6 1 4 6 7 8 10 5 1 4 6 7 9 6 1 4 6 7 9 10 5 1 4 6 7 10 4 1 4 6 8 5 1 4 6 8 9 6 1 4 6 8 9 10 5 1 4 6 8 10 4 1 4 6 9 5 1 4 6 9 10 4 1 4 6 10 3 1 4 7 4 1 4 7 8 5 1 4 7 8 9 6 1 4 7 8 9 10 5 1 4 7 8 10 4 1 4 7 9 5 1 4 7 9 10 4 1 4 7 10 3 1 4 8 4 1 4 8 9 5 1 4 8 9 10 4 1 4 8 10 3 1 4 9 4 1 4 9 10 3 1 4 10 2 1 5 3 1 5 6 4 1 5 6 7 5 1 5 6 7 8 6 1 5 6 7 8 9 7 1 5 6 7 8 9 10 6 1 5 6 7 8 10 5 1 5 6 7 9 6 1 5 6 7 9 10 5 1 5 6 7 10 4 1 5 6 8 5 1 5 6 8 9 6 1 5 6 8 9 10 5 1 5 6 8 10 4 1 5 6 9 5 1 5 6 9 10 4 1 5 6 10 3 1 5 7 4 1 5 7 8 5 1 5 7 8 9 6 1 5 7 8 9 10 5 1 5 7 8 10 4 1 5 7 9 5 1 5 7 9 10 4 1 5 7 10 3 1 5 8 4 1 5 8 9 5 1 5 8 9 10 4 1 5 8 10 3 1 5 9 4 1 5 9 10 3 1 5 10 2 1 6 3 1 6 7 4 1 6 7 8 5 1 6 7 8 9 6 1 6 7 8 9 10 5 1 6 7 8 10 4 1 6 7 9 5 1 6 7 9 10 4 1 6 7 10 3 1 6 8 4 1 6 8 9 5 1 6 8 9 10 4 1 6 8 10 3 1 6 9 4 1 6 9 10 3 1 6 10 2 1 7 3 1 7 8 4 1 7 8 9 5 1 7 8 9 10 4 1 7 8 10 3 1 7 9 4 1 7 9 10 3 1 7 10 2 1 8 3 1 8 9 4 1 8 9 10 3 1 8 10 2 1 9 3 1 9 10 2 1 10 2 2 3 3 2 3 4 4 2 3 4 5 5 2 3 4 5 6 6 2 3 4 5 6 7 7 2 3 4 5 6 7 8 8 2 3 4 5 6 7 8 9 9 2 3 4 5 6 7 8 9 10 8 2 3 4 5 6 7 8 10 7 2 3 4 5 6 7 9 8 2 3 4 5 6 7 9 10 7 2 3 4 5 6 7 10 6 2 3 4 5 6 8 7 2 3 4 5 6 8 9 8 2 3 4 5 6 8 9 10 7 2 3 4 5 6 8 10 6 2 3 4 5 6 9 7 2 3 4 5 6 9 10 6 2 3 4 5 6 10 5 2 3 4 5 7 6 2 3 4 5 7 8 7 2 3 4 5 7 8 9 8 2 3 4 5 7 8 9 10 7 2 3 4 5 7 8 10 6 2 3 4 5 7 9 7 2 3 4 5 7 9 10 6 2 3 4 5 7 10 5 2 3 4 5 8 6 2 3 4 5 8 9 7 2 3 4 5 8 9 10 6 2 3 4 5 8 10 5 2 3 4 5 9 6 2 3 4 5 9 10 5 2 3 4 5 10 4 2 3 4 6 5 2 3 4 6 7 6 2 3 4 6 7 8 7 2 3 4 6 7 8 9 8 2 3 4 6 7 8 9 10 7 2 3 4 6 7 8 10 6 2 3 4 6 7 9 7 2 3 4 6 7 9 10 6 2 3 4 6 7 10 5 2 3 4 6 8 6 2 3 4 6 8 9 7 2 3 4 6 8 9 10 6 2 3 4 6 8 10 5 2 3 4 6 9 6 2 3 4 6 9 10 5 2 3 4 6 10 4 2 3 4 7 5 2 3 4 7 8 6 2 3 4 7 8 9 7 2 3 4 7 8 9 10 6 2 3 4 7 8 10 5 2 3 4 7 9 6 2 3 4 7 9 10 5 2 3 4 7 10 4 2 3 4 8 5 2 3 4 8 9 6 2 3 4 8 9 10 5 2 3 4 8 10 4 2 3 4 9 5 2 3 4 9 10 4 2 3 4 10 3 2 3 5 4 2 3 5 6 5 2 3 5 6 7 6 2 3 5 6 7 8 7 2 3 5 6 7 8 9 8 2 3 5 6 7 8 9 10 7 2 3 5 6 7 8 10 6 2 3 5 6 7 9 7 2 3 5 6 7 9 10 6 2 3 5 6 7 10 5 2 3 5 6 8 6 2 3 5 6 8 9 7 2 3 5 6 8 9 10 6 2 3 5 6 8 10 5 2 3 5 6 9 6 2 3 5 6 9 10 5 2 3 5 6 10 4 2 3 5 7 5 2 3 5 7 8 6 2 3 5 7 8 9 7 2 3 5 7 8 9 10 6 2 3 5 7 8 10 5 2 3 5 7 9 6 2 3 5 7 9 10 5 2 3 5 7 10 4 2 3 5 8 5 2 3 5 8 9 6 2 3 5 8 9 10 5 2 3 5 8 10 4 2 3 5 9 5 2 3 5 9 10 4 2 3 5 10 3 2 3 6 4 2 3 6 7 5 2 3 6 7 8 6 2 3 6 7 8 9 7 2 3 6 7 8 9 10 6 2 3 6 7 8 10 5 2 3 6 7 9 6 2 3 6 7 9 10 5 2 3 6 7 10 4 2 3 6 8 5 2 3 6 8 9 6 2 3 6 8 9 10 5 2 3 6 8 10 4 2 3 6 9 5 2 3 6 9 10 4 2 3 6 10 3 2 3 7 4 2 3 7 8 5 2 3 7 8 9 6 2 3 7 8 9 10 5 2 3 7 8 10 4 2 3 7 9 5 2 3 7 9 10 4 2 3 7 10 3 2 3 8 4 2 3 8 9 5 2 3 8 9 10 4 2 3 8 10 3 2 3 9 4 2 3 9 10 3 2 3 10 2 2 4 3 2 4 5 4 2 4 5 6 5 2 4 5 6 7 6 2 4 5 6 7 8 7 2 4 5 6 7 8 9 8 2 4 5 6 7 8 9 10 7 2 4 5 6 7 8 10 6 2 4 5 6 7 9 7 2 4 5 6 7 9 10 6 2 4 5 6 7 10 5 2 4 5 6 8 6 2 4 5 6 8 9 7 2 4 5 6 8 9 10 6 2 4 5 6 8 10 5 2 4 5 6 9 6 2 4 5 6 9 10 5 2 4 5 6 10 4 2 4 5 7 5 2 4 5 7 8 6 2 4 5 7 8 9 7 2 4 5 7 8 9 10 6 2 4 5 7 8 10 5 2 4 5 7 9 6 2 4 5 7 9 10 5 2 4 5 7 10 4 2 4 5 8 5 2 4 5 8 9 6 2 4 5 8 9 10 5 2 4 5 8 10 4 2 4 5 9 5 2 4 5 9 10 4 2 4 5 10 3 2 4 6 4 2 4 6 7 5 2 4 6 7 8 6 2 4 6 7 8 9 7 2 4 6 7 8 9 10 6 2 4 6 7 8 10 5 2 4 6 7 9 6 2 4 6 7 9 10 5 2 4 6 7 10 4 2 4 6 8 5 2 4 6 8 9 6 2 4 6 8 9 10 5 2 4 6 8 10 4 2 4 6 9 5 2 4 6 9 10 4 2 4 6 10 3 2 4 7 4 2 4 7 8 5 2 4 7 8 9 6 2 4 7 8 9 10 5 2 4 7 8 10 4 2 4 7 9 5 2 4 7 9 10 4 2 4 7 10 3 2 4 8 4 2 4 8 9 5 2 4 8 9 10 4 2 4 8 10 3 2 4 9 4 2 4 9 10 3 2 4 10 2 2 5 3 2 5 6 4 2 5 6 7 5 2 5 6 7 8 6 2 5 6 7 8 9 7 2 5 6 7 8 9 10 6 2 5 6 7 8 10 5 2 5 6 7 9 6 2 5 6 7 9 10 5 2 5 6 7 10 4 2 5 6 8 5 2 5 6 8 9 6 2 5 6 8 9 10 5 2 5 6 8 10 4 2 5 6 9 5 2 5 6 9 10 4 2 5 6 10 3 2 5 7 4 2 5 7 8 5 2 5 7 8 9 6 2 5 7 8 9 10 5 2 5 7 8 10 4 2 5 7 9 5 2 5 7 9 10 4 2 5 7 10 3 2 5 8 4 2 5 8 9 5 2 5 8 9 10 4 2 5 8 10 3 2 5 9 4 2 5 9 10 3 2 5 10 2 2 6 3 2 6 7 4 2 6 7 8 5 2 6 7 8 9 6 2 6 7 8 9 10 5 2 6 7 8 10 4 2 6 7 9 5 2 6 7 9 10 4 2 6 7 10 3 2 6 8 4 2 6 8 9 5 2 6 8 9 10 4 2 6 8 10 3 2 6 9 4 2 6 9 10 3 2 6 10 2 2 7 3 2 7 8 4 2 7 8 9 5 2 7 8 9 10 4 2 7 8 10 3 2 7 9 4 2 7 9 10 3 2 7 10 2 2 8 3 2 8 9 4 2 8 9 10 3 2 8 10 2 2 9 3 2 9 10 2 2 10 2 3 4 3 3 4 5 4 3 4 5 6 5 3 4 5 6 7 6 3 4 5 6 7 8 7 3 4 5 6 7 8 9 8 3 4 5 6 7 8 9 10 7 3 4 5 6 7 8 10 6 3 4 5 6 7 9 7 3 4 5 6 7 9 10 6 3 4 5 6 7 10 5 3 4 5 6 8 6 3 4 5 6 8 9 7 3 4 5 6 8 9 10 6 3 4 5 6 8 10 5 3 4 5 6 9 6 3 4 5 6 9 10 5 3 4 5 6 10 4 3 4 5 7 5 3 4 5 7 8 6 3 4 5 7 8 9 7 3 4 5 7 8 9 10 6 3 4 5 7 8 10 5 3 4 5 7 9 6 3 4 5 7 9 10 5 3 4 5 7 10 4 3 4 5 8 5 3 4 5 8 9 6 3 4 5 8 9 10 5 3 4 5 8 10 4 3 4 5 9 5 3 4 5 9 10 4 3 4 5 10 3 3 4 6 4 3 4 6 7 5 3 4 6 7 8 6 3 4 6 7 8 9 7 3 4 6 7 8 9 10 6 3 4 6 7 8 10 5 3 4 6 7 9 6 3 4 6 7 9 10 5 3 4 6 7 10 4 3 4 6 8 5 3 4 6 8 9 6 3 4 6 8 9 10 5 3 4 6 8 10 4 3 4 6 9 5 3 4 6 9 10 4 3 4 6 10 3 3 4 7 4 3 4 7 8 5 3 4 7 8 9 6 3 4 7 8 9 10 5 3 4 7 8 10 4 3 4 7 9 5 3 4 7 9 10 4 3 4 7 10 3 3 4 8 4 3 4 8 9 5 3 4 8 9 10 4 3 4 8 10 3 3 4 9 4 3 4 9 10 3 3 4 10 2 3 5 3 3 5 6 4 3 5 6 7 5 3 5 6 7 8 6 3 5 6 7 8 9 7 3 5 6 7 8 9 10 6 3 5 6 7 8 10 5 3 5 6 7 9 6 3 5 6 7 9 10 5 3 5 6 7 10 4 3 5 6 8 5 3 5 6 8 9 6 3 5 6 8 9 10 5 3 5 6 8 10 4 3 5 6 9 5 3 5 6 9 10 4 3 5 6 10 3 3 5 7 4 3 5 7 8 5 3 5 7 8 9 6 3 5 7 8 9 10 5 3 5 7 8 10 4 3 5 7 9 5 3 5 7 9 10 4 3 5 7 10 3 3 5 8 4 3 5 8 9 5 3 5 8 9 10 4 3 5 8 10 3 3 5 9 4 3 5 9 10 3 3 5 10 2 3 6 3 3 6 7 4 3 6 7 8 5 3 6 7 8 9 6 3 6 7 8 9 10 5 3 6 7 8 10 4 3 6 7 9 5 3 6 7 9 10 4 3 6 7 10 3 3 6 8 4 3 6 8 9 5 3 6 8 9 10 4 3 6 8 10 3 3 6 9 4 3 6 9 10 3 3 6 10 2 3 7 3 3 7 8 4 3 7 8 9 5 3 7 8 9 10 4 3 7 8 10 3 3 7 9 4 3 7 9 10 3 3 7 10 2 3 8 3 3 8 9 4 3 8 9 10 3 3 8 10 2 3 9 3 3 9 10 2 3 10 2 4 5 3 4 5 6 4 4 5 6 7 5 4 5 6 7 8 6 4 5 6 7 8 9 7 4 5 6 7 8 9 10 6 4 5 6 7 8 10 5 4 5 6 7 9 6 4 5 6 7 9 10 5 4 5 6 7 10 4 4 5 6 8 5 4 5 6 8 9 6 4 5 6 8 9 10 5 4 5 6 8 10 4 4 5 6 9 5 4 5 6 9 10 4 4 5 6 10 3 4 5 7 4 4 5 7 8 5 4 5 7 8 9 6 4 5 7 8 9 10 5 4 5 7 8 10 4 4 5 7 9 5 4 5 7 9 10 4 4 5 7 10 3 4 5 8 4 4 5 8 9 5 4 5 8 9 10 4 4 5 8 10 3 4 5 9 4 4 5 9 10 3 4 5 10 2 4 6 3 4 6 7 4 4 6 7 8 5 4 6 7 8 9 6 4 6 7 8 9 10 5 4 6 7 8 10 4 4 6 7 9 5 4 6 7 9 10 4 4 6 7 10 3 4 6 8 4 4 6 8 9 5 4 6 8 9 10 4 4 6 8 10 3 4 6 9 4 4 6 9 10 3 4 6 10 2 4 7 3 4 7 8 4 4 7 8 9 5 4 7 8 9 10 4 4 7 8 10 3 4 7 9 4 4 7 9 10 3 4 7 10 2 4 8 3 4 8 9 4 4 8 9 10 3 4 8 10 2 4 9 3 4 9 10 2 4 10 2 5 6 3 5 6 7 4 5 6 7 8 5 5 6 7 8 9 6 5 6 7 8 9 10 5 5 6 7 8 10 4 5 6 7 9 5 5 6 7 9 10 4 5 6 7 10 3 5 6 8 4 5 6 8 9 5 5 6 8 9 10 4 5 6 8 10 3 5 6 9 4 5 6 9 10 3 5 6 10 2 5 7 3 5 7 8 4 5 7 8 9 5 5 7 8 9 10 4 5 7 8 10 3 5 7 9 4 5 7 9 10 3 5 7 10 2 5 8 3 5 8 9 4 5 8 9 10 3 5 8 10 2 5 9 3 5 9 10 2 5 10 2 6 7 3 6 7 8 4 6 7 8 9 5 6 7 8 9 10 4 6 7 8 10 3 6 7 9 4 6 7 9 10 3 6 7 10 2 6 8 3 6 8 9 4 6 8 9 10 3 6 8 10 2 6 9 3 6 9 10 2 6 10 2 7 8 3 7 8 9 4 7 8 9 10 3 7 8 10 2 7 9 3 7 9 10 2 7 10 2 8 9 3 8 9 10 2 8 10 2 9 10
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 2 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 2 2 2 4 4 4 5 4 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 5 5 8