408581: GYM103192 L 零时困境

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

L. 零时困境time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

当法伊、西格玛、戴安娜再次醒来时,发现他们又一次被关在了一个全新的密室中,有了之前几次的经验,他们显得并不吃惊。果然,密室里的小电视里,又出现了零的身影,他沙哑的嗓音也又一次从电视的扬声器中传出:"别担心,这次只要玩一个猜谜游戏,猜中了,你们就可以安全的离开这里"。

"零这家伙,一定又在捣什么鬼,我才不信他会有这么好心。"西格玛喃喃自语道。

游戏的规则是:

零首先写下一个$$$n$$$个数的全排列$$$\{p_n\}$$$,并告诉三人他选择的$$$n$$$。

接着,三人可以进行$$$m$$$次提问,每次提问,三个人每人给出一个数字,要求三个数字两两不相同,记为$$$i,j,k$$$,用于询问$$$p_i,p_j,p_k$$$中的中位数。接到提问后,零会如实回答三个数中中位数是哪一个,告知他们三人中位数的下标(即,零总是诚实地回答$$$i,j,k$$$三个数之一)。

现在,你知道了这$$$m$$$次提问的具体内容与零的回答,请你判断,三人是否可以通过这些信息$$$100\%$$$的确定零手中的排列。

备注:一个含有$$$n$$$个数的全排列$$$\{p_n\}$$$是指一个长为$$$n$$$且$$$1$$$到$$$n$$$的每个数都出现且仅出现一次的序列。例如,$$$[2,1,3],[3,1,2]$$$是全排列,而$$$[1,2,4],[2,3,3]$$$都不是全排列。

Input

输入的第一行是两个整数$$$n,m(1\leq n \leq 10^5,0\leq m \leq 10^5)$$$,表示全排列的长度与三人提出的询问数。

接下来$$$m$$$行,每行四个数字$$$i,j,k,ans(1\leq i,j,k,ans \leq n, ans \in \{i,j,k\})$$$表示一次提问,含义如题面所述。

保证每次提问的$$$i,j,k$$$互不相同但有可能出现相同的提问、保证至少有一个长为$$$n$$$的全排列可以满足所有的$$$m$$$次询问的信息。

Output

请输出一行字符串,若三人可以唯一确定该全排列,输出$$$YES$$$,否则输出$$$NO$$$。

ExampleInput
4 2
1 2 3 2
4 1 3 4
Output
NO
Note

对于样例,$$$[1,2,4,3]$$$,$$$[1,3,4,2]$$$,$$$[4,2,1,3]$$$,$$$[4,3,1,2]$$$都是满足条件的全排列,因此三人无法确定全排列到底是什么。

加入题单

上一题 下一题 算法标签: