1259 : Game on a Forest
- 时间限制Time Limit
- 1 秒Sec
- 内存限制Memory Limit
- 256 兆MB
- 提交次数Submitted
- 94 次Times
- 通过次数Solved
- 49 次Times
| 比对Compare | token 相同即通过。中间的空格、制表符、换行可多可少。Matching tokens pass. Extra spaces, tabs, or newlines between them are ignored. |
|---|---|
| 不同则错Differs | token 个数或内容不同即错误。23 与 2 3、02 与 2、2.0 与 2 均视为不同。A different token count or value is wrong. 23 vs 2 3, 02 vs 2, and 2.0 vs 2 all differ. |
| 输入Input | 标准输入,格式见题面。Standard input; format as in the statement. |
| 输出Output | 标准输出。Standard output. |
| 时间与内存Time and memory | 记这一份程序的 CPU 时间和内存峰值。题目上的时间限制、内存限制就是这一份的上限。The record is this program’s CPU time and peak memory. The limits on the problem apply to this one run. |
题目描述Description
Plover and Georgia are playing a game on a forest graph. Given is an (a forest) with \(n\) nodes and \(m\) edges. Now, Plover and Georgia take turns operating on the graph, with Georgia starting first.
Each operation must be one of the following types:
- Select an edge in the graph. Then remove it.
- Select a node in the graph. Then remove both the node and the edges attached to it.
When one of them is unable to operate on his/her turn(which means the graph is empty), the game is lost and the other one wins. Now, assuming that Plover and Georgia are both extremely smart, Georgia wants to know how many different first moves can make her win the game.
输入格式Input
The first line contains two integers \(n,m(1\le m<n\le 10^5 )\) , indicating the number of nodes and the number of edges, respectively.
For the next \(m\) lines, the \(i\)-th line contains two integers \(u_i,v_i(1\le u_i<v_i\le n)\), indicating an edge connected the \(u_i\)-th node and the \(v_i\)-th node.
It is guaranteed that for all \(i,j(1\le i<j\le m)\),\(u_i\ne u_j\) or \(v_i\ne v_j\) is satisfied.
输出格式Output
Output contains an integer \(W(0\le W\le n+m)\), indicating the number of different first moves that can make Georgia win.
样例Sample
提示Hint
For the first sample, if Georgia selects node \(1\) or node \(2\) for the first move, she can win the game.
For the second sample, if Georgia selects any one of the \(3\) edges for the first move, she can win the game.
出题Author
FUDAN