하한이 있는 유량

정점이 $N$개이고 간선이 $M$개인 방향 그래프가 주어진다. 정점의 번호는 $0$부터 $N-1$까지이다. 각 간선에는 유량의 하한 $l$과 상한 $r$이 있으며, 그 간선의 유량은 $l$ 이상 $r$ 이하인 정수여야 한다. 자기 루프와 중복 간선이 있을 수 있다.

정점의 순유량은 나가는 유량의 합에서 들어오는 유량의 합을 뺀 값이다. 서로 다른 두 정점 $S$, $T$와 질의의 종류 $K$가 주어질 때 다음 값을 구해 보자.

• $K=0$: 모든 정점의 순유량이 $0$인 유량 배치가 존재하는지 판별한다.
• $K=1$: $S$, $T$를 제외한 모든 정점의 순유량이 $0$이고, $S$의 순유량이 음이 아닌 유량 배치가 존재하는지 판별한다.
• $K=2$: $K=1$의 조건을 만족하는 배치 중 $S$의 순유량의 최댓값을 구한다.

$S$의 순유량이 음수인 배치만 가능하다면 $K=1$과 $K=2$의 조건을 만족하지 않는다.

첫 번째 줄에 테스트 케이스의 수를 의미하는 정수 $Q$가 주어진다. $(1 \le Q \le 200)$

각 테스트 케이스의 첫 번째 줄에 다섯 정수 $K$, $N$, $M$, $S$, $T$가 공백으로 구분되어 주어진다. $(0 \le K \le 2; 2 \le N \le 1\,000; 0 \le M \le 10\,000; 0 \le S, T < N; S \ne T)$ $K=0$일 때 $S$, $T$는 결과에 영향을 주지 않는다.

두 번째 줄부터 $M$개의 줄에 걸쳐 간선의 시작 정점 번호 $u$, 끝 정점 번호 $v$와 유량의 하한과 상한을 나타내는 두 정수 $l$, $r$이 공백으로 구분되어 주어진다. $(0 \le u, v < N; 0 \le l \le r \le 10^9)$

전체 테스트 케이스에서 $N$의 합은 $10\,000$ 이하이고 $M$의 합은 $50\,000$ 이하이다.

각 테스트 케이스마다 답을 한 줄에 출력한다. $K=0$ 또는 $K=1$일 때는 조건을 만족하는 유량 배치가 있다면 $1$을, 그렇지 않다면 $0$을 출력한다. $K=2$일 때는 $S$의 순유량의 최댓값을 출력하고, 조건을 만족하는 유량 배치가 없다면 $-1$을 출력한다.