U123309 4269. 【NOIP2015模拟10.27】挑竹签

#### [题解](https://www.cnblogs.com/wondering-world/p/13376256.html)

挑竹签——小时候的游戏 夏夜，早苗和诹访子在月光下玩起了挑竹签这一经典的游戏。 挑竹签，就是在桌上摆上一把竹签，每次从最上层挑走一根竹签。如果动了其他的竹签，就要换对手来挑。在所有的竹签都被挑走之后，谁挑走的竹签总数多，谁就胜了。 身为神明的诹访子自然会让早苗先手。为了获胜，早苗现在的问题是，在诹访子出手之前最多能挑走多少竹签呢？ 为了简化问题，我们假设当且仅当挑最上层的竹签不会动到其他竹签。

第一行输入两个整数$n,m$, 表示竹签的根数和竹签之间相压关系数。 第二行到$m+1$ 行每行两个整数$u,v$，表示第$u$ 根竹签压住了第$v $根竹签。

一共一行，一个整数$sum$，表示最多能拿走$sum$ 根竹签。

对于$20\%$ 的数据，有$1 \le n,m \le 20$。 对于$40\%$ 的数据，有$1 \le n,m \le 1 000$。 对于$100\%$ 的数据，有$1 \le n,m \le 1 000 000。$ 样例解释： 一共有$6$ 根竹签，其中$1$ 压住$2，2$ 压住$3，3$ 压住$1，4$ 压住$3$ 和$5，6$ 压住$5$。最优方案中，我们可以依次挑走$4、6、5 $三根竹签。而剩下的三根相互压住，都无法挑走。所以最多能挑走$3$ 根竹签。