In a country there are \(n\) cities. The cities are connected by \(m\) bus routes, where
the \(i-th\) route starts in city \(a_{i}\), ends in city \(b_{i}\) and takes \(t_{i}\) minutes.
Ema loves to travel, but doesn’t like transferring between buses. On her trip
she wants to use at most \(k\) different bus routes.
Help her answer \(q\) questions of the form ‘What is the shortest travel time to
get from city \(c_{j}\) to city \(d_{j}\) (using at most \(k\) different bus routes)?’.

Subtask 1 (15 points): \(k \le n \le 7\)

Subtask 2 (15 points): \(k \le 3\)

Subtask 3 (25 points): \(k \le n\)

Subtask 4 (15 points): No additional constraints.

The first line contains two positive integers \(n\) and \(m\) (\(2 \le n \le 70\), \(1 \le m \le 10^{6}\)), the number of cities and
the number of bus routes.
The \(i-th\) of the next \(m\) lines contains positive integers \(a@@RISE_MATH_BLOCK_0@@i\) and \(t@@RISE_MATH_BLOCK_1@@i\), b\(i \le n\), \(1 \le t\)\(i \le 10^{6}\)), the
terminal cities and the travel time of the \(i-th\) bus route.
The next line contains two positive integers \(k\) and \(q\) (\(1 \le k \le 10^{9}\), \(1 \le q \le n\)^{2}), the maximum number of
used routes and the number of queries.
The \(j-th\) of the next \(q\) lines contains positive integers \(c_{j}\) and \(d_{j}\) (\(1 \le c_{j}\), \(d_{j} \le n\)), the cities from the \(j-th\)
query.

Print \(q\) lines. In the \(j-th\) line print the shortest travel time from the \(j-th\) query, \(or -1\) if there is no trip
that satisfies the requirements.

생성자가 기록되지 않았습니다.

출처 COCI 2021/2022 Contest 4