#P18056. Outsmarting

    ID: 17392 传统题 1000ms 1024MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-配对策略二分图匹配暴力枚举顶点覆盖最小割建模最大流最小割定理Edmonds–Karp残量网络

Outsmarting

Outsmarting

给定一个无向二分图。左侧有 nUn_U 个顶点,编号为 1,…,nU1,\ldots,n_U;右侧有 nVn_V 个顶点,编号为 1,…,nV1,\ldots,n_V。每个顶点有启用或禁用两种状态。左侧顶点 11 初始启用。

两名玩家轮流移动一个棋子,初始棋子位于左侧顶点 11。每次必须沿一条边,将棋子移动到一个启用的相邻顶点,并将刚刚离开的顶点永久禁用。无法进行合法移动的玩家失败,双方都采用最优策略。

游戏开始前,你可以翻转一些顶点的初始状态:启用改为禁用,禁用改为启用。每个顶点最多翻转一次,且不能翻转左侧顶点 11。

求使先手必胜所需的最少翻转次数。若无法做到,输出 −1-1。

输入格式

第一行三个整数 nU,nV,mn_U,n_V,m,其中 1≤nU,nV≤1001\le n_U,n_V\le100,0≤m≤nUnV0\le m\le n_Un_V。

接下来 mm 行,每行两个整数 u,vu,v,表示左侧顶点 uu 与右侧顶点 vv 相连。

下一行 nUn_U 个 0/10/1 整数 sU,1,…,sU,nUs_{U,1},\ldots,s_{U,n_U},随后一行 nVn_V 个 0/10/1 整数 sV,1,…,sV,nVs_{V,1},\ldots,s_{V,n_V},其中 11 表示启用,00 表示禁用,保证 sU,1=1s_{U,1}=1。

输出格式

输出一个整数,表示最少翻转次数;不可能时输出 −1-1。

样例

输入:

4 4 8
1 1
2 1
2 2
3 1
3 3
4 2
4 3
4 4
1 1 1 1
1 1 1 0

输出:

1