AtCoder 町有 个交叉路口和 条道路。 第 条道路连接交叉路口 和交叉路口 。
町长打算在 AtCoder 町的交叉路口上安装 个或更多的监控摄像头。 每个交叉路口最多只能安装 个监控摄像头，也可以不安装。
监控摄像头的安装方式共有 种，其中有多少种安装方式能使被监控的道路数为偶数？
这里，道路 被称为“被监控”，当且仅当：
交叉路口 和交叉路口 中，至少有一个安装了监控摄像头。
输入以如下格式从标准输入读入。
请输出答案。
3 2 1 2 2 3
6
20 3 5 6 3 4 1 2
458752
选择安装监控摄像头的交叉路口为 、、、、、 时，均满足条件。注意也可以一个监控摄像头都不安装。
AtCoder 町不一定是连通的。
