Description

Rumia: There are $n$ fairies who want to cross Mist Lake. Because the lakeside is covered in thick fog, the fairies cannot tell how big the lake is and do not want to walk around the edge.

There is a boat teleporter on the lake, and each time this teleporter can carry at most $r$ fairies across the lake (note that the teleporter can simultaneously send fairies from both sides to the opposite side, but the total number moved in one operation must not exceed $r$).

These fairies love to make trouble, so at all times the following conditions must be satisfied. There are $m_1$ conditions of the first type and $m_2$ conditions of the second type.

First type: Fairy $a$ and fairy $b$ must be on the same side of the lake.

Second type: When fairy $a$ is on one side of the lake, fairies $b$ and $c$ must not be simultaneously on the other side.

Given these conditions, find:

1. The minimum number of times the teleporter must be used to move all fairies to the opposite shore.
2. Under the constraint of using the minimum number of times, the number of valid crossing plans.

Input Format

The first line contains four integers $n, m_1, m_2, r$.

Each of the next $m_1$ lines contains two integers $a, b$, representing a condition of the first type.

Each of the next $m_2$ lines contains three integers $a, b, c$, representing a condition of the second type.

Output Format

Output two integers: the minimum number of uses of the teleporter and the number of valid plans, separated by a space.

If it is impossible for all fairies to cross, output -1 0.

1 0 0 1

1 1

5 0 0 2

3 90

3 1 0 1
1 2

-1 0

Hint

• For $30\%$ of the testdata, $n \leq 10$.
• For another $10\%$ of the testdata, $m_1 = m_2 = 0$.
• Constraints: For $100\%$ of the testdata, $a, b, c \leq n \leq 15$, $m_1, m_2 \leq 50$, $r \leq 10^9$.

Please do not rely on the Luogu judge’s speed. If you score above $80$, you can submit again when there are fewer users. But if you score below $60$, it probably is not the correct solution, so please do not put extra load on the judge.

Translated by ChatGPT 5