The Big Two の解説

答えはab[0]の(a, b)どちらかが含まれるのは確定。

では、答えにaが含まれる時に相方として釣り合うのは、aが含まれないindex全てに値があるもの。

これらを列挙して判定してあげれば良い。

探索の際には一見O(n^2)かかってしまいそうだけど、値は合計で 2 * n個しかないので適切にbreakなどすれば探索を合計最大2 * nまで落とせるので間に合う。

fn main() {
    input! {
        n: usize, m: usize,
        ab: [(Usize1, Usize1); m]
    }
    let f = |v: usize| {
        let mut ans = vec![];
        for i in 0..m {
            let (a, b) = ab[i];
            if a != v && b != v {
                ans.push(i);
            }
        }
        ans
    };
    let (aa, bb) = ab[0];
    let v1 = f(aa);
    let v2 = f(bb);

    let map = {
        let mut map = vec![HashSet::new(); n];
        for i in 0..m {
            let (a, b) = ab[i];
            map[a].insert(i);
            map[b].insert(i);
        }
        map
    };

    let mut ans = HashSet::new();
    let f2 = |v: usize, ans: &mut HashSet<(usize, usize)>, vv: &Vec<usize>| {
        'la: for i in 0..n {
            if i == v {
                continue;
            }
            for &idx in vv.iter() {
                if !map[i].contains(&idx) {
                    continue 'la;
                }
            }
            let aa = min(i, v);
            let bb = max(i, v);
            ans.insert((aa, bb));
        }
    };
    f2(aa, &mut ans, &v1);
    f2(bb, &mut ans, &v2);

    println!("{}", ans.len());
}