U479513 过河问题

农夫需要带狼、羊、菜过河；船上只能坐两个东西；只有农夫可以划船；当狼和羊单独在一起时，狼会吃羊；羊和菜单独在一起时，羊会吃菜；求全部过河的合法解。 该题为上述题的扩展版。

现有`n`个人，他们要过河，有一艘船，船上可以坐两个人；过河后船要有人开回来。现有`m`对关系`(a,b)`，表示`a`和`b`单独在一起时会打架。求给出的数据能否满足所有人都过河。 **备注** 1.两个有关系的人在船上会打架，不能一起坐船 2.只有两个人单独在一起时会打架；三个人一起的时候，即使互相不顺眼，也不会打架。 3.所有人都会开船。

输入一个整数`N`，代表数据组数。 对于每组数据，第一行输入两个整数`n`和`m`，意义同题目描述。 接下来m行，每一行两个整数`a`和`b`，意义同题目描述。

对于每组数据，输出一行，若该组数据有可行解，输出`Yes`，否则输出`No`。

对于所有的`N`满足：$1