#P18056. Outsmarting
Outsmarting
Outsmarting
给定一个无向二分图。左侧有 个顶点,编号为 ;右侧有 个顶点,编号为 。每个顶点有启用或禁用两种状态。左侧顶点 初始启用。
两名玩家轮流移动一个棋子,初始棋子位于左侧顶点 。每次必须沿一条边,将棋子移动到一个启用的相邻顶点,并将刚刚离开的顶点永久禁用。无法进行合法移动的玩家失败,双方都采用最优策略。
游戏开始前,你可以翻转一些顶点的初始状态:启用改为禁用,禁用改为启用。每个顶点最多翻转一次,且不能翻转左侧顶点 。
求使先手必胜所需的最少翻转次数。若无法做到,输出 。
输入格式
第一行三个整数 ,其中 ,。
接下来 行,每行两个整数 ,表示左侧顶点 与右侧顶点 相连。
下一行 个 整数 ,随后一行 个 整数 ,其中 表示启用, 表示禁用,保证 。
输出格式
输出一个整数,表示最少翻转次数;不可能时输出 。
样例
输入:
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