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] == 3) { Graph g2 = g.copy(); g2.delete_v_with_neighbours(A); Pair p2 = ms(g2); p2.cardinality++; p2.choosed_vertices[A] = true; ArrayList d = new ArrayList<>(); for (int i = 0; i < e[A].size(); i++) { d.add(e[A].get(i)); } g.delete_vertice(A); Pair p1 = ms2(g, A, 0, d); 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; if (p1.cardinality > p2.cardinality) { return p1; } else { return p2; } } // 頂点vの隣接頂点から少なくとも二つ使う場合を考える。 // count==1なら2回目 // count==0なら1回目 Pair ms2(Graph g, int v, int count, ArrayList neighbour) { 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]); while(!neighbour.isEmpty()) { int u = neighbour.get(0); if (!valid_vertices[u]) { if(!neighbour.remove((Integer)u)){ throw new AssertionError("neighbour dosent have u"); } if(count==0) throw new AssertionError("error"); continue; } if (deg[u] <= 1) { g.delete_v_with_neighbours(u); if(!neighbour.remove((Integer)u)){ throw new AssertionError("neighbour dosent have u"); } if (count == 0) { Pair p1 = ms2(g, v, (count + 1), neighbour); p1.choosed_vertices[u] = true; p1.cardinality++; return p1; } else if (count == 1) { Pair p1 = ms(g); p1.choosed_vertices[u] = true; p1.cardinality++; return p1; } else { throw new AssertionError("error"); } } Graph g2 = g.copy(); g2.delete_v_with_neighbours(u); if(!neighbour.remove((Integer)u)){ throw new AssertionError("neighbour dosent have u"); } if (count == 0) { Pair p2 = ms2(g2, v, (count + 1), neighbour); p2.choosed_vertices[u] = true; p2.cardinality++; p = pair_bigger(p,p2); } else if (count == 1) { Pair p2 = ms(g2); p2.choosed_vertices[u] = true; p2.cardinality++; p = pair_bigger(p, p2); } else { throw new AssertionError("error"); } } if(neighbour.size()!=0){ throw new AssertionError("neighbour.size()=="+neighbour.size()); } return p; } Pair pair_bigger(Pair p1, Pair p2) { return p1.cardinality > p2.cardinality ? p1 : p2; } class Pair { int cardinality; boolean[] choosed_vertices; Pair(int cardinality, boolean[] choosed_vertices) { this.cardinality = cardinality; this.choosed_vertices = choosed_vertices; } } // whethere N(B)&B is subset of N(A)&A or not; boolean dominance(int A, int B, Graph g) { Setas = 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; } }