小学数学题

题目背景

露米娅:我来先考你一道小学数学题吧! 琪露诺:好!小学的题我肯定都会!

题目描述

露米娅:有 $ n $ 只妖精要跨过雾之湖,由于湖边大雾弥漫,妖精们看不清湖到底有多大,不想从边上绕过去。 湖上有一~~条船~~个传送器,且这个传送器每次只能载 $ r $ 只妖精跨过湖面(注意传送器可以同时把两侧的妖精分别运到对岸,但每次运送的总妖精数不能超过 $ r $ )。 这些妖精还很喜欢搞事,所以在任何时刻,都需要满足一些条件,其中第一种条件有 $ m_1 $ 个,第二种条件有 $ m_2 $ 个。 第一种条件形如 妖精 $ a $ 和妖精 $ b $ 必须要在湖的同一侧; 第二种条件形如 当妖精 $ a $ 在湖的一侧时,妖精 $ b $ 和妖精 $ c $ 不能同时在湖的另一侧。 现在给出这些条件,求: 1. 至少需要传送器几次才能让所有妖精到湖的对岸 2. 在保证次数最少的前提下,求过河方案数

输入输出格式

输入格式


第一行四个整数 $ n , m_1 , m_2 , r $ 接下来 $ m_1 $ 行每行2个整数 $ a , b $,代表第一种条件 接下来 $ m_2 $ 行每行3个整数 $ a , b , c $, 代表第二种条件

输出格式


两个整数,分别为最少使用传送器次数和方案数,用空格分隔 若无法全部过河,输出"-1 0"(不含引号)

输入输出样例

输入样例 #1

1 0 0 1

输出样例 #1

1 1

输入样例 #2

5 0 0 2

输出样例 #2

3 90

输入样例 #3

3 1 0 1
1 2

输出样例 #3

-1 0

说明

对于 $ 30 \% $ 的数据, $ n \leq 10 $ 对于另外 $ 10 \% $ 的数据, $ m_1 = m_2 = 0 $ 对于 $ 100 \% $ 的数据, $ a,b,c \leq n \leq 15 $, $ m_1 , m_2 \leq 50 $, $ r \leq 10^9 $ 请不要相信洛谷评测机的速度,如果得了80分以上,可以等人少的时候再交一次。但如果得了60分以下,说明可能写的不是正解,就不要再虐萌萌哒评测机啦