#P9607. 题

    ID: 6222 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>CF2200提高+/省选-逆向思考位集求交组合枚举

题

题目描述

一开始有 nn 个苹果,mm 个人依次来吃苹果,第 ii 个人会尝试吃 uiu_i 或 viv_i 号苹果,具体来说分三种情况。

  1. 两个苹果都还在,那么这个人将随便选一个苹果吃了。
  2. 只有一个苹果,那么这个人将吃掉这个苹果。
  3. 都不在了,这个人吃不到苹果就走了。

请问有多少对无序苹果对 (i,j)(i,j) 满足它们两个都幸存下来的概率 >0> 0。

输入格式

第一行两个整数 n,mn, m。

接下来 mm 行,每行两个整数 ui,viu_i , v_i。

输出格式

一个整数表示答案。

样例

4 3
1 2
3 4
2 3
1

只有 (1,4)(1, 4) 满足条件。

数据范围

  • 对于测试点 1∼51\sim 5,n,m≤20n,m\le 20。
  • 对于测试点 5∼85\sim 8,若把苹果看做点,人看做边,那么会形成一棵树。
  • 对于测试点 9∼159\sim 15,m≤400m\le 400。
  • 对于测试点 16∼2516\sim 25,无特殊限制。

对于所有的数据,1≤n≤4001\le n\le 400,1≤m≤5×1041\le m\le 5\times 10^4。