该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem 7E. 不想走回头路的Pac-Man

时间限制：1000ms

空间限制：256MB

题目背景

Pac-Man也就是吃豆人被认为是80年代最经典的街机游戏之一。该游戏的背景以黑色为主。主要的场景在迷宫中，四个颜色分别为红、黄、蓝、绿的鬼面符号在迷宫中穿梭，在寻找一个半开半合的黄色圆圈符号。黄色圆圈符号可以行走，并且可以吞吃迷宫路径上的小黄豆，但遇到鬼面符号时就会被吃掉。

题目描述

贪吃的吃豆人（Pac-Man）想要吃掉一张地图上的所有豆子，但是小红（Blinky）今天追的出奇的紧，因此他想要找到一种方法不回头的（不能走重复的路径）吃完所有的豆子。
地图上有n个节点，记作0到n-1号点，我们的吃豆人在0号点上，节点直接存在着m条无向边连接，每个边上都有许多豆子。总的来说，吃豆人现在需要找到这么一条路径，从0号点开始，不重复的走完所有边。
注意，边可以链接同一个节点，可以有多条相同的边，不保证全部连通。

输入格式

第一行一个整数T，表示有T组测试样例。
接下来每组样例第一行，两个整数n和m，表示点数和边数。
然后m行，每行两个整数，表示一条边。

输出格式

输出T个数字，1代表可以找到符合条件的路径，0代表找不到符合条件的路径。

样例输入1

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

样例输出1

1
0

数据范围及约定

对于50%，\(T \le 10,n \le 10,m \le 45\)。
对于100%，\(T \le 100\)，n的总和不大于1e5，nm的总和不大于5*1e5。