// 以下の提出を多大に参考にしている // https://yukicoder.me/submissions/471192 type BIT = u128; struct Graph { size: usize, edge: Vec, } impl Graph { fn new(size: usize) -> Self { assert!(std::mem::size_of::() * 8 >= size); Graph { size: size, edge: (0..size).map(|x| (1 as BIT) << x as BIT).collect(), } } fn add_edge(&mut self, s: usize, t: usize) { assert!(s != t); self.edge[s] |= (1 as BIT) << t as BIT; self.edge[t] |= (1 as BIT) << s as BIT; } fn rec(&self, rem: BIT) -> Vec { if rem == 0 { return vec![]; } let mut max_deg = (0, 0); let mut bit = rem; while bit > 0 { let x = bit & (!bit + 1); bit -= x; let x = x.trailing_zeros() as usize; let deg = (self.edge[x] & rem).count_ones(); if deg <= 2 { let mut ans = self.rec(rem & !self.edge[x]); ans.push(x); return ans; } max_deg = std::cmp::max(max_deg, (deg, x)); } let v = max_deg.1; let mut ans = self.rec(rem & !self.edge[v]); ans.push(v); if max_deg.0 <= 3 { return ans; } let q = self.rec(rem & !((1 as BIT) << v as BIT)); if q.len() > ans.len() { q } else { ans } } fn solve(&self) -> Vec { let mask = if self.size == std::mem::size_of::() * 8 { !0 } else { ((1 as BIT) << self.size as BIT) - 1 }; self.rec(mask) } } struct RNG { s: usize } impl RNG { fn new(seed: usize) -> Self { RNG { s: seed, } } fn next(&mut self) -> usize { self.s = self.s * 12345 % 1000003; self.s } } fn run() { let mut s = String::new(); std::io::stdin().read_line(&mut s).unwrap(); let mut rng = RNG::new(s.trim().parse().unwrap()); let n: usize = rng.next() % 120 + 2; let mut graph = Graph::new(n); let p = rng.next(); for i in 1..=n { for j in (i + 1)..=n { let e = rng.next(); if e >= p { graph.add_edge(i - 1, j - 1); } } } let ans = graph.solve(); let mut out = String::new(); out.push_str(&format!("{}\n", ans.len() + 1)); for a in ans { out.push_str(&format!("{} ", a + 1)); } out.pop(); println!("{}", out); } fn main() { run(); }