给定一张 nnn 个点 mmm 条边的无向图,每条边居黑白二色之一,且有一个黑或白的目标颜色.
有一辆卡车,可以从任意一个结点开始,经过一个简单环(不经过重复边或起点以外结点的环)回到出发点,将所有经过边的颜色反转,即黑色变为白色,白色变为黑色.卡车可以从不同的结点出发行走若干次.
请给出一个合法的方案,使得每条边最终都变为目标颜色,或判定不可行.
输入的第一行包含两个空格分隔的正整数 nnn 和 mmm,表示图的点数和边数.
你可以认为若存在合法方案,则存在一个卡车经过总边数不超过 5m5m5m 的方案.
否则按下列格式输出任意一种方案:
第一行包含一个整数 kkk,表示卡车行驶环路的总数;
首先是一个正整数 kik_iki  表示环路经过的边数,后接一个空格;
接下来 ki+1k_i + 1ki +1 个空格分隔的整数,依次表示环路上结点的编号.
读题可知本题需要在图中求出若干个欧拉回路.
显然,没有改变权值的边可以直接忽略掉.之后计算每个点的度数,根据欧拉回路的定义,图中不能存在度数为奇数的点,如果发现图中存在度数为奇数的点则无解.