Handel

어떤 무역 연합에 속한 나라들이 연합 내부 거래에 쓰는 금액을 검토하고 있다. 연합에는 $1$번부터 $N$번까지 번호가 매겨진 $N$개의 나라가 있으며, 이 나라들은 나라 사이의 거래액을 제한하는 조건을 모두 $M$개 제출했다.

각 조건은 네 개의 수 $a$, $b$, $l$, $h$로 주어지며, 나라 $a$가 나라 $b$의 물품을 최소 $l$, 최대 $h$의 금액으로 사고 싶어 함을 뜻한다.

최신 연합 지침에 따르면 각 회원국의 내부 거래 수지는 반드시 $0$이어야 한다. 즉 각 나라에 대해, 그 나라가 다른 나라들에 판매한 금액의 합은 그 나라가 다른 나라들로부터 구매한 금액의 합과 정확히 같아야 한다.

모든 조건과 이 수지 균형 지침을 동시에 만족하도록 각 조건마다 거래 금액을 하나씩 정하는 것이 가능한지 판별하여라.

첫째 줄에 테스트 집합의 개수를 나타내는 정수 $Z$ ($Z = 1$)가 주어진다. 이어서 각 테스트 집합이 주어진다.

각 테스트 집합의 첫째 줄에는 두 정수 $N$과 $M$ ($1 \le N \le 150$, $0 \le M \le 1500$)이 주어진다. 각각 나라의 수와 조건의 수이다. 다음 $M$개의 줄에는 각 조건이 주어지며, $i$번째 줄에는 네 정수 $a_i$, $b_i$, $l_i$, $h_i$ ($1 \le a_i, b_i \le N$, $0 < l_i \le h_i \le 150000$)가 주어진다. 이는 나라 $a_i$가 나라 $b_i$의 물품을 사는 데 $l_i$ 이상 $h_i$ 이하의 금액을 쓰고 싶어 함을 뜻한다. 어떤 나라도 자기 자신과는 거래하지 않으며, 순서쌍 $(a_i, b_i)$는 모두 서로 다르다. 거래는 주어진 쌍 사이에서만 이루어진다.

각 테스트 집합에 대해, 모든 거래 금액을 각자의 범위 안에서 정하면서 모든 나라의 총판매액과 총구매액이 같아지도록 만들 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.