blob: e2640920e57273148378ef785162e20270f85d49 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
use std::{
collections::{BTreeSet, HashMap},
io::Read,
iter::repeat,
};
fn main() {
let mut input = String::new();
std::io::stdin().read_to_string(&mut input).unwrap();
let mut lines = input.lines();
let mut nm = lines.next().unwrap().split_ascii_whitespace();
let n: usize = nm.next().unwrap().parse().unwrap();
let m: usize = nm.next().unwrap().parse().unwrap();
let mut covers = HashMap::<usize, Vec<usize>>::with_capacity(m);
let mut n_above = vec![0usize; n];
let mut sticks_at: Vec<BTreeSet<usize>> = repeat(BTreeSet::new()).take(m).collect();
for i in 0..n {
sticks_at[0].insert(i);
}
for mut line in lines.map(str::split_ascii_whitespace) {
let a = line.next().unwrap().parse::<usize>().unwrap() - 1;
let b = line.next().unwrap().parse::<usize>().unwrap() - 1;
covers.entry(a).or_default().push(b);
sticks_at[n_above[b]].remove(&b);
n_above[b] += 1;
sticks_at[n_above[b]].insert(b);
}
let mut picks = Vec::with_capacity(n);
loop {
let stick = if let Some(&s) = sticks_at[0].iter().next() {
s
} else {
break;
};
sticks_at[0].remove(&stick);
picks.push(stick);
if let Some(c) = covers.get(&stick) {
for &b in c {
sticks_at[n_above[b]].remove(&b);
n_above[b] -= 1;
sticks_at[n_above[b]].insert(b);
}
}
}
if picks.len() != n {
println!("IMPOSSIBLE");
return;
}
for p in picks {
println!("{}", p + 1);
}
}
|
