/ Vijos / 题库 /

神秘配方

神秘配方

背景

每天中午的下课铃一响,浙江镇海中学的同学们都会冲出学校来附近的小饭馆吃饭,刹那间天昏地暗,飞砂走石,家家餐馆内都是一片黑压压的人 。馄饨店、饺子馆,在学校附近开一家红一家。身为镇海中学信息中心首席科学顾问兼资深信息学竞赛辅导老师Dennis看到了,他为了在业余时间方便学生,他租了学校附近的一家店面,雇了几个拉面师傅,开了一家“正宗兰州牛肉拉面馆”,生意还不错。

描述

Dennis的拉面馆隆重开张后,虽然生意很好,但是由于Dennis相信“没有最好,只有更好”(就像他对算法复杂度的不懈追求),于是他带领着他的徒弟光光和娃娃一起来到拉面的故乡——甘肃的兰州,寻找传说中世界上最好吃的拉面……
在当地人的指导下,Dennis 一行来到了一个偏僻的小村子,传说这个村子就盛产世界上最好吃的拉面。可是Dennis很快发现了这个村子的村民的奇特之处:这些村名喜欢说谎话。由于完全说谎话很容易会被识破,所以他们会有时说真话而有时说假话,好在经过调查,光光已经知道了村民的这个习俗。为了获得传说中美味拉面的神秘配方,Dennis精心设计了n个问题,每个问题只需回答“是”或“否”就行,然后根据答案,他就能得到拉面的秘方。于是光光和娃娃问了m个不同的村民,对于每个村民,从n个问题中挑出2个不同的问题问他,并纪录下答案交予Dennis统计。可是Dennis发现这样的统计太复杂和困难了,于是他想知道根据村名的回答,n个问题的答案可能有的情况总数。

格式

输入格式

第一行是两个整数n(1<=n<=200),m(0<=m<=10000),分别表示Dennis准备了n个问题,问了m个不同的村名。接下去m行,第i+1行有四个整数a,b,c,d(1<=a,c<=n),表示第i个村民对第a个问题的答案是b,对第c个问题的答案是d。当b或d是0时表示答案为“否”,是1时表示答案为“是”。一个村民在回答时不会中途改变其说谎性,即他要么一直说真话,要么一直说假话。但我们不知道他到底在说真话还是假话。

输出格式

一个整数,表示可能的情况总数。如果不可能,则输出“No Answer”

样例1

样例输入1

2 2
1 1 2 0
1 1 2 1

样例输出1

No Answer

样例2

样例输入2

4 4
1 1 2 1
1 1 3 0
2 1 4 1
3 1 4 0

样例输出2

2

限制

共10点,每点1秒。

提示

30%的数据,n<=10,m<=100
100%的数据,n<=200,m<=10000
样例解释:
对于样例1-----第一个村民的回答要求题1和题2的答案不同(即如果他在说谎,那么问题1答案是No,问题2答案是Yes,如果他没有说谎,那么问题1答案是Yes,问题2答案是No,总之不一样),第二个村名的回答要求题1和题2的答案相同,故矛盾
对于样例2-----2种可能的情况分别为(问题1-4答案)
Yes-yes-no-yes 或者No-no-no-yes
如果Dennis一个人也没有问,那么答案总数就是2^n了不是?
温馨提示:最后的情况总数可能很大。本题是图论题。

来源

fangyuhua&ycglovewxx