Problem

Given two jug capacities jug1 and jug2, and a target amount target, return the minimum number of operations needed to measure exactly target liters. An operation is one of: fill a jug completely, empty a jug, or pour water from one jug to the other until either the source is empty or the destination is full. If it is impossible, return -1.

Examples

Example 1:

Input: jug1 = 3, jug2 = 5, target = 4
Output: 6
Explanation: One optimal sequence reaches 4 liters in the 5-liter jug in 6 operations.

Example 2:

Input: jug1 = 2, jug2 = 6, target = 5
Output: -1
Explanation: It is impossible to measure exactly 5 liters using these jug sizes.

Constraints

• 1 <= jug1, jug2 <= 10^3
• 0 <= target <= jug1 + jug2
• Each state is represented by the current water amounts in the two jugs