题目背景

露米娅：我来先考你一道小学数学题吧！

琪露诺：好！小学的题我肯定都会！

题目描述

露米娅：有 $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 0 0 1

1 1

5 0 0 2

3 90

3 1 0 1
1 2

-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分以下，说明可能写的不是正解，就不要再虐萌萌哒评测机啦