//! # Bundled libraries //! //! - `procon_reader 0.1.0 (git+https://github.com/ia7ck/rust-competitive-programming#bd4907c0d20d80d0c7a19f92b3bb682e6326d08d)` licensed under **missing** as `crate::__cargo_equip::crates::procon_reader` pub use __cargo_equip::prelude::*; use procon_reader::ProconReader; fn main() { let stdin = std::io::stdin(); let mut rd = ProconReader::new(stdin.lock()); let h: usize = rd.get(); let w: usize = rd.get(); let n: usize = rd.get(); let mut cities = Vec::new(); let mut g = vec![vec![]; h + w]; for i in 0..n { let x: usize = rd.get(); let y: usize = rd.get(); cities.push((x, y)); g[x - 1].push((h + (y - 1), i)); g[h + (y - 1)].push((x - 1, i)); } let mut seen_node = vec![false; h + w]; let mut seen_edge = vec![false; n]; for u in 0..(h + w) { if seen_node[u] { continue; } let mut cycle = Vec::new(); dfs(u, &g, &mut seen_node, &mut seen_edge, &mut cycle); if cycle.is_empty() { continue; } assert!(cycle.len() >= 4); cycle.reverse(); let (_, y0) = cities[cycle[0]]; let (_, y1) = cities[cycle[1]]; let (_, y2) = cities[cycle[2]]; if y0 != y1 { assert_eq!(y1, y2); cycle.rotate_left(1); } println!("{}", cycle.len()); for t in cycle { // println!("{:?}", cities[t]); print!("{} ", t + 1); } return; } println!("-1"); } fn dfs( u: usize, g: &Vec>, seen_node: &mut Vec, seen_edge: &mut Vec, cycle: &mut Vec, ) -> Option<(bool, usize)> { seen_node[u] = true; for &(v, idx) in &g[u] { if seen_edge[idx] { continue; } seen_edge[idx] = true; if seen_node[v] { cycle.push(idx); return Some((false, v)); } if let Some((finish, head)) = dfs(v, g, seen_node, seen_edge, cycle) { if finish { return Some((finish, head)); } cycle.push(idx); return Some((u == head, head)); } } None } // The following code was expanded by `cargo-equip`. #[rustfmt::skip] #[allow(unused)] mod __cargo_equip { pub(crate) mod crates { pub mod procon_reader {use std::io::BufRead;use std::str::FromStr;pub struct ProconReader{r:R,l:String,i:usize,}implProconReader{pub fn new(reader:R)->Self{Self{r:reader,l:String::new(),i:0,}}pub fn get(&mut self)->T where T:FromStr,::Err:std::fmt::Debug,{self.skip_blanks();assert!(self.i{self.i+=j;break;}None=>{let mut buf=String::new();let num_bytes=self.r.read_line(&mut buf).unwrap_or_else(|_|panic!("invalid UTF-8"));assert!(num_bytes>0,"reached EOF :(");self.l=buf.trim_end_matches('\n').trim_end_matches('\r').to_string();self.i=0;}}}}pub fn get_vec(&mut self,n:usize)->Vecwhere T:FromStr,::Err:std::fmt::Debug,{(0..n).map(|_|self.get()).collect()}pub fn get_chars(&mut self)->Vec{self.get::().chars().collect()}}} } pub(crate) mod macros { pub mod procon_reader {} } pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;} mod preludes { pub mod procon_reader {} } }