package yukicoder; import java.util.ArrayList; import java.util.Arrays; import java.util.HashSet; import java.util.Iterator; import java.util.Scanner; import java.util.Set; public class Main { public static void main(String[] args) { new Main().solver(); // new Q382().trial(); } void trial() { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] d = new int[N - 1]; for (int i = 0; i < N - 1; i++) { d[i] = sc.nextInt(); } Arrays.sort(d); for (int i = 0; i < N - 1; i++) { System.out.println(d[i]); } } void solver() { Scanner sc = new Scanner(System.in); long S = sc.nextLong(); long Start = System.currentTimeMillis(); Graph g = set_edge(S); Pair p = ms(g); int n = g.n; if (p.cardinality == n) { System.out.println(-1); } else { System.out.println((p.cardinality + 1)); boolean f = false; for (int i = 0; i < p.choosed_vertices.length; i++) { if (p.choosed_vertices[i]) { System.out.print((!f ? "" : " ") + (i + 1)); f = true; } } System.out.println(); } long T = System.currentTimeMillis(); System.err.println((T - Start) + "ms"); } final long MOD = 1000003; Graph set_edge(long S) { S = (S * 12345) % MOD; int N = (int) (S % 120) + 2; Graph g = new Graph(N); S = (S * 12345) % MOD; long P = S; for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { S = (S * 12345) % MOD; if (S >= P) { g.set_edge(i, j); } } } return g; } // 無向グラフ class Graph { ArrayList[] e; int n; int[] deg; boolean[] valid_vertices;// 選ぶことのできる頂点 boolean[] choosed_vertices;// 選ばれた頂点 Graph(int n) { this.n = n; deg = new int[n]; valid_vertices = new boolean[n]; choosed_vertices = new boolean[n]; Arrays.fill(valid_vertices, true); e = new ArrayList[n]; for (int i = 0; i < n; i++) { e[i] = new ArrayList<>(); } } // 無向グラフの辺a<->を作成 void set_edge(int a, int b) { if (!e[a].contains((Integer) b)) { e[a].add(b); e[b].add(a); deg[a]++; deg[b]++; } } // 辺a<->bを消去 void delete_undirected_edge(int a, int b) { e[a].remove((Integer) b); e[b].remove((Integer) a); deg[a]--; deg[b]--; } // 頂点vを消去 void delete_vertice(int v) { while (e[v].size() > 0) { int u = e[v].get(0); delete_undirected_edge(u, v); } valid_vertices[v] = false; } // 頂点vと、vの隣接頂点を消去 void delete_v_with_neighbours(int v) { while (e[v].size() > 0) { int u = e[v].get(0); delete_vertice(u); } delete_vertice(v); } // deep copy Graph copy() { Graph g = new Graph(this.n); for (int i = 0; i < n; i++) { g.deg[i] = deg[i]; } for (int i = 0; i < n; i++) { g.valid_vertices[i] = valid_vertices[i]; } for (int i = 0; i < n; i++) { for (int j = 0; j < e[i].size(); j++) { (g.e[i]).add(e[i].get(j)); } } return g; } } Pair ms(Graph g) { int[] deg = g.deg; ArrayList[] e = g.e; boolean[] valid_vertices = g.valid_vertices; int n = g.n; int A = -1;// 最も次数の小さい頂点 int B = -1;// Aにつながる頂点のうち最も次数の大きいもの int deg_me_min = Integer.MAX_VALUE / 4; int deg_to_max = -Integer.MAX_VALUE / 4; for (int i = 0; i < n; i++) { if (!valid_vertices[i]) continue; if (deg[i] < deg_me_min) { A = i; deg_me_min = deg[A]; if (deg_me_min <= 1) { g.delete_v_with_neighbours(A); Pair p = ms(g); p.choosed_vertices[A] = true; p.cardinality++; return p; } B = e[A].get(0); deg_to_max = deg[B]; for (int j = 1; j < e[A].size(); j++) { int u = e[A].get(j); if (deg[u] > deg_to_max) { B = u; deg_to_max = deg[B]; } } } else if (deg[i] == deg_me_min) { for (int j = 0; j < e[A].size(); j++) { int u = e[A].get(j); if (deg[u] > deg_to_max) { A = i; B = u; deg_to_max = deg[B]; } } } } if (A == -1 && B == -1) return new Pair(0, new boolean[n]); if (A == -1 || B == -1) throw new AssertionError("A==-1||B==-1"); if (deg[A] > deg[B]) throw new AssertionError("deg[A]>deg[B]"); if (deg[A] == 2) { int B2 = -1; if (e[A].get(0) != B) { B2 = e[A].get(0); } else if (e[A].get(1) != B) { B2 = e[A].get(1); } if (edge(B2,B,e)) { g.delete_v_with_neighbours(A); Pair p = ms(g); p.cardinality++; p.choosed_vertices[A] = true; return p; }else{ Graph g2 = g.copy(); g2.delete_v_with_neighbours(B); g2.delete_v_with_neighbours(B2); Pair p = ms(g2); p.cardinality += 2; p.choosed_vertices[B] = true; p.choosed_vertices[B2] = true; ArrayList neighbour = new ArrayList<>(); for (int i = 0; i < 2; i++) { int u = (i == 0 ? B : B2);// u is an element of N(A) for (int j = 0; j < e[u].size(); j++) { int v = e[u].get(j); if (v == A) continue; if (neighbour.contains(v)) continue; neighbour.add(v); } } g.delete_v_with_neighbours(A); Pair p2 = ms2(g, neighbour); p2.cardinality++; p2.choosed_vertices[A] = true; p = pair_bigger(p, p2); return p; } } if (deg[A] == 3) { Graph g2 = g.copy(); ArrayList S=new ArrayList<>(); for (int i = 0; i < e[A].size(); i++) { S.add(e[A].get(i)); } g.delete_vertice(A); Pair p1 = ms2(g, S); g2.delete_v_with_neighbours(A); Pair p2 = ms(g2); p2.cardinality++; p2.choosed_vertices[A] = true; return pair_bigger(p1, p2); } // else if (dominance(B, A, g)) { // g.delete_vertice(B); // Pair p = ms(g); // p.cardinality++; // p.choosed_vertices[B] = true; // return p; // } Graph g2 = g.copy(); g2.delete_v_with_neighbours(B); g.delete_vertice(B); Pair p1 = ms(g); Pair p2 = ms(g2); p2.cardinality++; p2.choosed_vertices[B] = true; return pair_bigger(p1, p2); } // Sから少なくとも二つ使う場合を考える。 Pair ms2(Graph g, ArrayList S) { int[] deg = g.deg; ArrayList[] e = g.e; boolean[] valid_vertices = g.valid_vertices; int n = g.n; Pair p = new Pair(0, new boolean[n]); if (S.size() <= 1) return p; else if (S.size() == 2) { int u = S.get(0); int v = S.get(1); if (e[u].contains(v)) return p; else { g.delete_v_with_neighbours(u); g.delete_v_with_neighbours(v); p = ms(g); p.cardinality += 2; p.choosed_vertices[u] = true; p.choosed_vertices[v] = true; return p; } } else if (S.size() == 3) { int[] s = new int[3]; for (int i = 0; i < 3; i++) { s[i] = S.get(i); } // arrange s[i] so that s[0] is the smallest one; if (deg[s[0]] > deg[s[1]]) { int d = s[0]; s[0] = s[1]; s[1] = d; } if (deg[s[0]] > deg[s[2]]) { int d = s[0]; s[0] = s[2]; s[2] = d; } if (deg[s[0]] == 0) { g.delete_vertice(s[0]); S.remove((Integer) s[0]); if (is_deg_correct(e, deg)) { throw new AssertionError(); } p = ms1(g, S); p.cardinality++; p.choosed_vertices[s[0]] = true; return p; } else if (edge(s[0], s[1], e) && edge(s[1], s[2], e) && edge(s[2], s[0], e)) { return p; } for (int i = 0; i < 3; i++) { int u = s[(i + 1) % 3]; int v = s[(i + 2) % 3]; if (edge(u, s[i], e) && edge(s[i], v, e)) { g.delete_v_with_neighbours(u); g.delete_v_with_neighbours(v); p = ms(g); p.cardinality += 2; p.choosed_vertices[u] = true; p.choosed_vertices[v] = true; return p; } } for (int i = 0; i < 3; i++) { int u = s[(i + 1) % 3]; int v = s[(i + 2) % 3]; if (edge(u, v, e)) { g.delete_v_with_neighbours(s[i]); S.remove((Integer) s[i]); p = ms1(g, S); p.cardinality++; p.choosed_vertices[s[i]] = true; return p; } } for (int i = 0; i < 3; i++) { int u = s[i]; int v = s[(i + 1) % 3]; ArrayList intersection = intersection(e[u], e[v]); if (intersection.size() >= 1) { int w = intersection.get(0); g.delete_vertice(w); p = ms2(g, S); return p; } } if (deg[s[0]] == 1) { g.delete_v_with_neighbours(s[0]); S.remove((Integer) s[0]); p = ms1(g, S); p.cardinality++; p.choosed_vertices[s[0]] = true; return p; } else { Graph g2 = g.copy(); g2.delete_v_with_neighbours(s[0]); S.remove((Integer) s[0]); p = ms1(g2, S); p.cardinality++; p.choosed_vertices[s[0]] = true; g.delete_v_with_neighbours(s[2]); g.delete_v_with_neighbours(s[1]); ArrayList S2 = new ArrayList<>(); for (int i = 0; i < e[s[0]].size(); i++) { S2.add(e[s[0]].get(i)); } g.delete_vertice(s[0]); Pair p2 = ms2(g, S2); return pair_bigger(p, p2); } } if (S.size() <= 3) throw new AssertionError(); if (S.size() == 4) { int min_v = S.get(0); for (int i = 0; i < 4; i++) { int v = S.get(i); if (deg[v] < deg[min_v]) { min_v = v; } } if (deg[min_v] <= 3) { return ms(g); } else { Graph g2 = g.copy(); g.delete_v_with_neighbours(min_v); p = ms(g); p.cardinality++; p.choosed_vertices[min_v] = true; g2.delete_vertice(min_v); S.remove((Integer) min_v); Pair p2 = ms2(g2, S); return pair_bigger(p, p2); } } if (S.size() <= 4) throw new AssertionError(); return ms(g); } Pair ms1(Graph g, ArrayList S) { int[] deg = g.deg; ArrayList[] e = g.e; boolean[] valid_vertices = g.valid_vertices; int n = g.n; if (S.size() != 2) { throw new AssertionError("S.size()!=2"); } int s1 = S.get(0); int s2 = S.get(1); if (deg[s1] > deg[s2]) { int d = s1; s1 = s2; s2 = d; } if (deg[s1] <= 1) { return ms(g); } else if (edge(s1,s2,e)) { if (deg[s1] <= 3) return ms(g); else { Graph g2 = g.copy(); g.delete_v_with_neighbours(s1); Pair p1 = ms(g); p1.cardinality++; p1.choosed_vertices[s1] = true; g2.delete_v_with_neighbours(s2); Pair p2 = ms(g2); p2.cardinality++; p2.choosed_vertices[s2] = true; return pair_bigger(p1, p2); } } ArrayList intersection = intersection(e[s1], e[s2]); if (intersection.size() != 0) { for (int i = 0; i < intersection.size(); i++) { g.delete_vertice(intersection.get(i)); } return ms1(g, S); } else if (deg[s2] == 2) { if (deg[s1] != 2) { throw new AssertionError("deg[s1]!=2"); } int E = e[s1].get(0); int F = e[s1].get(1); if (is_deg_correct(e, deg)) { throw new AssertionError(); } if (edge(E,F,e)) { g.delete_v_with_neighbours(s1); Pair p = ms(g); p.cardinality++; p.choosed_vertices[s1] = true; return p; } if (is_deg_correct(e, deg)) { throw new AssertionError(); } ArrayList union = union(e[E], e[F]); union.remove((Integer) s1); if (is_deg_correct(e, deg)) { throw new AssertionError(); } if (is_subset(union, e[s2])) { g.delete_v_with_neighbours(E); g.delete_v_with_neighbours(F); g.delete_v_with_neighbours(s2); Pair p = ms(g); p.cardinality += 3; p.choosed_vertices[E] = true; p.choosed_vertices[F] = true; p.choosed_vertices[s2] = true; return p; } else { Graph g2 = g.copy(); g.delete_v_with_neighbours(E); g.delete_v_with_neighbours(F); g.delete_v_with_neighbours(s2); Pair p = ms(g); p.cardinality += 3; p.choosed_vertices[E] = true; p.choosed_vertices[F] = true; p.choosed_vertices[s2] = true; g2.delete_v_with_neighbours(s1); Pair p2 = ms(g2); p2.cardinality++; p2.choosed_vertices[s1] = true; return pair_bigger(p, p2); } } else { Graph g2 = g.copy(); g.delete_v_with_neighbours(s2); Pair p = ms(g); p.cardinality++; p.choosed_vertices[s2]=true; g2.delete_v_with_neighbours(s1); ArrayList S2=new ArrayList<>(); for(int i=0;ias = new HashSet<>(); Set bs = new HashSet<>(); ArrayList[] e = g.e; for (int i = 0; i < e[A].size(); i++) { as.add(e[A].get(i)); } for (int i = 0; i < e[B].size(); i++) { bs.add(e[B].get(i)); } if (!as.contains(B)) { as.add(B); } if (!bs.contains(A)) { bs.add(A); } if (as.size() < bs.size()) return false; for (Iterator it = bs.iterator(); it.hasNext();) { if (!as.contains(it.next())) { return false; } } return true; } boolean is_subset(ArrayList subset, ArrayList superset) { if (subset.size() > superset.size()) return false; for (int i = 0; i < subset.size(); i++) { if (!superset.contains(subset)) { return false; } } return true; } ArrayList union(ArrayList s1, ArrayList s2) { ArrayList ret = new ArrayList<>(); for (int i = 0; i < s1.size(); i++) { if (!ret.contains(s1.get(i))) { ret.add(s1.get(i)); } } for (int i = 0; i < s2.size(); i++) { if (!ret.contains(s2.get(i))) { ret.add(s2.get(i)); } } return ret; } // 正しくないときにtrueを返す boolean is_deg_correct(ArrayList[] e, int[] deg) { for (int i = 0; i < deg.length; i++) { if (deg[i] != e[i].size()) return true; } return false; } // 頂点u,v間に辺が存在するときtrueを返す。 boolean edge(int u, int v, ArrayList[] e) { if (e[u].contains(v)) return true; else return false; } @SuppressWarnings({ "rawtypes", "unchecked" }) ArrayList intersection(ArrayList s1, ArrayList s2) { ArrayList ret = new ArrayList<>(); for (int i = 0; i < s1.size(); i++) { if (s2.contains(s1.get(i))) { ret.add(s1.get(i)); } } return ret; } Pair pair_bigger(Pair p1, Pair p2) { return p1.cardinality > p2.cardinality ? p1 : p2; } }