fork download
  1. #include<iostream>
  2. #include<vector>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<unordered_set>
  6. using namespace std;
  7.  
  8. vector<int> edge[200005];
  9. int anc[20][200005]; // parent node
  10. int level[200005], sbtr[200005]; // depth node dan jumlah node pada subtree
  11. int in[200005], out[200005]; // buat cek subtree
  12. int visited[200005], revcutter;
  13. int powerofTwo[21];
  14. unordered_set<int> cutter; // cutter untuk menandai subtree yang membatasi jawaban, revcutter untuk menandai subtree yang
  15. int lg = 18, timer, ans_dist, ans;
  16.  
  17. void dfs(int now, int par){
  18. anc[0][now] = par; level[now] = level[par]+1;
  19. visited[now] = 1;
  20. in[now] = timer++;
  21. for(int dst : edge[now]) if(dst != par) dfs(dst, now);
  22. out[now] = timer++;
  23. }
  24.  
  25. int last_dfs(int now, int par){
  26. int x = 1;
  27. for(int dst : edge[now]) if(dst != par && !cutter.count(dst) && (anc[0][revcutter] != dst)) x += last_dfs(dst, now);
  28. return x;
  29. }
  30.  
  31. void addEdge(int src, int dst){
  32. edge[src].emplace_back(dst);
  33. edge[dst].emplace_back(src);
  34. }
  35.  
  36. int lca(int x, int y){
  37. if(level[x] < level[y])
  38. swap(x,y);
  39.  
  40. for(int i = lg; i >= 0; i--)
  41. if((level[x] - (1 << i)) >= level[y])
  42. x = anc[i][x];
  43.  
  44. if(x == y) return x;
  45.  
  46. for(int i = lg; i>=0; i--){
  47. if(anc[i][x] != anc[i][y]){
  48. x = anc[i][x]; y = anc[i][y];
  49. }
  50. }
  51. return anc[0][x];
  52. }
  53.  
  54. int distance(int x, int y){
  55. return level[x] + level[y] - 2 * level[lca(x,y)];
  56. }
  57.  
  58. // is y subtree of x
  59. bool isSubtree(int x, int y){
  60. return (in[x] <= in[y] && out[x] >= out[y]);
  61. }
  62.  
  63. int solve(int x, int y){
  64. if(anc[18][x] != anc[18][y]) return 0;
  65.  
  66. int anc_depth = level[lca(x,y)];
  67. int dist_x = level[x] - anc_depth, dist_y = level[y] - anc_depth;
  68. int dist = dist_x + dist_y;
  69. int to_root = dist + ans_dist;
  70. int mid = to_root >> 1, node;
  71.  
  72. if(to_root % 2){
  73. return 0;
  74. }
  75.  
  76. for(auto element: cutter){
  77. if(isSubtree(element, y)){
  78. if(dist == ans_dist) return x;
  79. return 0;
  80. }
  81. }
  82. if(revcutter && !isSubtree(revcutter, y)){
  83. if(dist == ans_dist) return x;
  84. return 0;
  85. }
  86.  
  87. if(dist == ans_dist){
  88. if(isSubtree(x,y)){
  89. if(ans_dist){
  90. node = y;
  91. for(int i = lg; i >= 0; i--)
  92. if((ans_dist - 1) & powerofTwo[i])
  93. node = anc[i][node];
  94. cutter.insert(node);
  95. }
  96. }
  97. else revcutter = x;
  98. return x;
  99. }
  100.  
  101. cutter.clear();
  102. revcutter = 0;
  103.  
  104. if(dist_y > mid){
  105. node = y;
  106. for(int i=lg; i>=0; i--){
  107. if((mid-1) & powerofTwo[i]) {
  108. node = anc[i][node];
  109. }
  110. }
  111. cutter.insert(node);
  112. revcutter = anc[0][node];
  113. }
  114. else if(dist_y == mid){
  115. node = y;
  116. for(int i=lg; i>=0; i--){
  117. if((mid-1) & powerofTwo[i]) {
  118. node = anc[i][node];
  119. }
  120. }
  121. cutter.insert(node);
  122.  
  123. node = x;
  124. for(int i=lg; i>=0; i--){
  125. if((mid-1-ans_dist) & powerofTwo[i]) {
  126. node = anc[i][node];
  127. }
  128. }
  129. cutter.insert(node);
  130. }
  131. else{
  132. node = x;
  133. for(int i=lg; i>=0; i--){
  134. if((mid-1-ans_dist) & powerofTwo[i]) {
  135. node = anc[i][node];
  136. }
  137. }
  138. cutter.insert(node);
  139. revcutter = anc[0][node];
  140. }
  141. ans_dist = mid;
  142. return anc[0][node];
  143. }
  144.  
  145. int main()
  146. {
  147. ios_base::sync_with_stdio(0);
  148. cin.tie(0); cout.tie(0);
  149. anc[0][0] = 0;
  150. int n; cin >> n;
  151. // while((1 << lg) < n)
  152. // lg++;
  153. int u,v,k;
  154. for(int i=0;i<n-1;i++) {
  155. cin >> u >> v >> k;
  156. if(k) addEdge(u, v);
  157. }
  158.  
  159. // binary lifting preprocessing
  160. memset(visited, 0, sizeof(visited));
  161. for(int i=1; i<=n; i++){
  162. if(!visited[i]) dfs(i,i);
  163. }
  164.  
  165. powerofTwo[0]=1;
  166. for(int i=1;i<=lg;i++){
  167. powerofTwo[i] = powerofTwo[i-1] << 1;
  168. for(int j=1;j<=n;j++){
  169. anc[i][j] = anc[i-1][anc[i-1][j]];
  170. }
  171. }
  172.  
  173. int q; cin >> q;
  174. int center; // jumlah node yang memenuhi dan tumpuan penghitungan node yang memenuhi
  175.  
  176. while(q--){
  177. revcutter = 0, ans_dist = 0;
  178. cutter.clear();
  179. int peeps,x; cin >> peeps;
  180. cin >> center;
  181. for(int i=0;i<(peeps-1);i++){
  182. cin >> x;
  183. // cout << center << endl;
  184. if(!center){
  185. continue;
  186. }
  187. center = solve(center, x);
  188. }
  189. if(center){
  190. cout << last_dfs(center, center) << '\n';
  191. }
  192. else cout << "0\n";
  193. }
  194.  
  195. return 0;
  196. }
Success #stdin #stdout 0.01s 26616KB
stdin
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
stdout
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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