Fairy Crossing with Constraints

There are n fairies that need to cross a foggy lake. Due to the heavy fog, they cannot see the full extent of the lake and do not want to go around the edge. Instead, they use a teleporter located in the middle of the lake.

The teleporter can simultaneously transport fairies from both sides, but in each operation the total number of fairies moved (from either side) cannot exceed r. That is, if you move some fairies from the left bank to the right bank and some from the right bank to the left bank in one move, the sum of both counts must not exceed r.

However, these fairies love mischief, so at any moment the following constraints must hold:

• Type-1 constraints: There are m₁ conditions. Each is of the form: "Fairy a and fairy b must be on the same side of the lake." In mathematical form, for each pair \( (a,b) \), we require that \[ side(a)=side(b). \]
• Type-2 constraints: There are m₂ conditions. Each is of the form: "When fairy a is on one side of the lake, fairies b and c cannot both be on the opposite side." If we denote a fairy being on the right bank as 1 and on the left bank as 0, then for each triple \( (a,b,c) \), the condition is: \[ \text{if } side(a)=0, \text{ then not }\big( side(b)=1 \text{ and } side(c)=1\big), \] \[ \text{if } side(a)=1, \text{ then not }\big( side(b)=0 \text{ and } side(c)=0\big). \]

Initially, all fairies are on the left bank (side 0) and the goal is to have all fairies on the right bank (side 1).

Your task is to determine:

1. The minimum number of teleporter operations required to get all fairies to the right bank.
2. Under the constraint of using the minimum number of operations, the number of valid crossing schemes.
</p>

inputFormat

The input is given as follows:

n r m1 m2
[a1 b1]
[a2 b2]
... (m1 lines for type-1 constraints)
[a1 b1 c1]
[a2 b2 c2]
... (m2 lines for type-2 constraints)

All fairies are numbered from 1 to n. The constraints are applied on fairies using 1-indexed numbering.

outputFormat

Output two space-separated integers:

1. The minimum number of teleporter operations required.
2. The number of valid crossing schemes achieving this minimum.

sample

3 2 1 0
1 2

2 1