NC213953. RikkawithGameTheory
描述
Game theory is an interesting subject in computer science.
SG function is an important concept in game theory. Given a directed acyclic graph
with vertex set 
and directed edge set 
, for each vertex 
, its SG function sg(u) is defined as:
%20%3D%20%5Ctext%7Bmex%7D(%5C%7Bsg(v)%7C%20(u%2Cv)%20%5Cin%20E_1%5C%7D))
where given a set S of non-negative integers,)
is defined as the smallest non-negative integer which is not in S.
Today, Rikka wants to generalize SG function to undirected graphs. Given an undirected graph G with vertex set V and undirected edge set E, a function f over V is a valid SG function on G if and only if:
Under this definition, there may be many valid SG functions for a graph. Therefore, Rikka wants to further figure out whether there is a connection between these valid SG functions. As the first step, your task is to calculate the number of valid SG functions for a given undirected graph G.
SG function is an important concept in game theory. Given a directed acyclic graph
where given a set S of non-negative integers,
Today, Rikka wants to generalize SG function to undirected graphs. Given an undirected graph G with vertex set V and undirected edge set E, a function f over V is a valid SG function on G if and only if:
- For each vertex
, f(u) is a non-negative integer;
- For each vertex
.
输入描述
The first line contains two integers, representing the number of vertices and edges in the graph.
Then m lines follow. Each line contains two integers, representing an edge in the graph.
The input guarantees that there are no loops and duplicate edges in the graph.
输出描述
Output a single line with a single integer, representing the number of valid SG functions.
示例1
输入:
5 4 1 2 2 3 3 4 4 5
输出:
6
说明:
For simplicity, we use listFor the sample input, there are 6 valid SG functions: [0,1,0,1,0], [0,1,2,0,1], [0,2,1,0,1], [1,0,1,0,1], [1,0,1,2,0] and [1,0,2,1,0].