小月的交换

题号：NC307936
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给定一个简单无向图 $G=(V,E)$ （顶点编号 $1,2,\dots,n$ ，边编号 $1,2,\dots,m$ ），每条边上有一个二值标记（ $0$ 或 $1$ ）。定义一次操作：
$\hspace{23pt}\bullet\,$ 任选图中两条相邻边（即它们在 $G$ 中共享一个公共端点），交换这两条边上的标记。
$\hspace{15pt}$ 现在，给定初始边标记字符串 $x$ （长度 $m$ ，仅由字符 $\texttt{`0'}$ 与 $\texttt{`1'}$ 组成）和目标标记字符串 $y$ ，判断是否可以通过若干次操作，使得 $x$ 变为 $y$ 。若可以，求最少操作次数。

【名词解释】
$\hspace{15pt}$ 简单无向图：指无重边、无自环的无向图。更具体地，若某条无向边连接顶点 $u$ 和 $v$ ，则 $u$ 和 $v$ 之间只有一条边，且 $u\neq v$ 。

输入描述:

第一行输入两个整数 ，表示图的顶点数量、边数量。
此后  行，第  行输入两个整数 ，表示图上第  条边双向连接顶点  和 。
第  行输入一个长度为 ，仅由字符  与  组成的字符串 ，表示初始边标记。
第  行输入一个长度为 ，仅由字符  与  组成的字符串 ，表示目标边标记。

输出描述:

如果无法通过操作得到 ，则输出 ，否则，第一行输出 ，第二行中输出最少需要的变换次数。

示例1

输入

复制

输出

复制

YES
2

说明

在这个样例中，交换第一条边和第二条边的标记，交换第三条边和第四条边的标记即可。

示例2

输入

复制

输出

复制

NO