Valid Seat Bookings

You are given an integer T representing the number of test cases. For each test case, you are provided with two integers N and M, where N (the number of stations) is not used, and M represents the number of seat bookings. Following this, there are M lines each containing three integers: s (starting station), e (ending station), and k (seat number).

A booking is valid if, for each seat, no two journeys overlap. Two journeys on the same seat (with intervals \( [s,e) \)) do not overlap if \( e \leq st \) or \( s \geq en \) holds, where \( [st,en) \) is a previously recorded journey on that seat.

Your task is to check whether all bookings in each test case are valid. Print "VALID" if all bookings are valid or "INVALID" if there exists any overlapping booking for a seat.

inputFormat

The first line of input contains a single integer T, the number of test cases.

For each test case:

• The first line contains two integers N and M, where N is the total number of stations (unused) and M is the number of bookings.
• The next M lines each contain three integers s, e, and k, describing a booking starting at station s, ending at station e on seat k.

outputFormat

For each test case, output a single line containing "VALID" if all bookings are valid, otherwise output "INVALID".

1
5 3
1 3 2
2 4 2
3 5 2

INVALID