1529：欧拉回路

题目描述

欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？

输入格式

输入包含若干个测试样例。每个测试样例的第一行给出两个正整数，分别是节点数 $N$ ($1 < N < 1000$) 和边数 $M$；随后的 $M$ 行对应 $M$ 条边。每行给出两个正整数，分别是该条边直接连接的两个节点的编号（节点从 $1$ 到 $N$ 编号）。当 $N$ 为 $0$ 时输入结束。

输出格式

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

样例

样例输入 #1

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

样例输出 #1

1
0

样例解释 #1

第一个测试样例：

• $N=3, M=3$。
• 边：$1-2$, $1-3$, $2-3$。
• 这是一个无向完全图 $K_3$，每个顶点的度数均为 $2$（偶数），且图连通，所以存在欧拉回路。输出 $1$。

第二个测试样例：

• $N=3, M=2$。
• 边：$1-2$, $2-3$。
• 这是一个链 $1-2-3$，顶点 $1$ 和 $3$ 的度数为 $1$（奇数），不满足欧拉回路条件（无向图欧拉回路要求所有顶点度数为偶数）。输出 $0$。

数据范围

• $1 < N < 1000$
• 图是无向的（根据输入格式，边是双向的）。

时空限制

• 时间限制：1000 ms
• 内存限制：262144 KB

注意：本题判断无向图是否存在欧拉回路。条件：

1. 图是连通的（可以通过 DFS/BFS/并查集判断）。
2. 所有顶点的度数都是偶数。

由于 $N < 1000$，可以直接用邻接矩阵或邻接表存储。注意处理重边和自环（自环会增加度数 $2$，不影响奇偶性；重边按多条边计算度数）。输入以 $N=0$ 结束。