题目描述

小明喜欢画图画，最近迷上了画连笔画。于是他想解决七桥问题，但是久久不能解决于是他向度娘查询了。原来欧拉大神已经解决了。并给出了证明（牛逼啊！！！） 现在有一个图请你帮小明判断是存在欧拉回路。 欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？ 现在科普时间到了！！！ 欧拉路径 指该路径经过图的每一条边且仅经过一次。 欧拉回路 如果路径起点和终点相同，则称“欧拉回路”。

无向图存在欧拉回路的充要条件 


一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图是连通图。(顶点度数为每个点连接出去的节点数)


有向图存在欧拉回路的充要条件 


一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。

（注意本题为无向图）

输入格式

测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是节点数N ( 1 束。

输出格式

每个测试用例的输出占一行，若欧拉回路存在则输出1，否则输出0。

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

1
0

提示

没有提示 就是菜  hdu原题目http://acm.hdu.edu.cn/showproblem.php?pid=1878 还不懂欧拉回路自行百度（本人比较水没能出一道dfs和fleury算法）