Session Scheduling Feasibility

Problem Statement

You are given the scheduling information for several branches of an organization. Each branch has a number of available rooms and contains two sets of sessions: existing sessions and planned sessions.

Your task is to determine whether all the planned sessions can be added into the branch's schedule without causing any overlap in any room. A session is represented by its start and end times (both integers). A session can be scheduled in a room if it does not overlap with any other session already scheduled in that room.

Formally, for each branch, you are given:

• An integer R representing the number of available rooms.
• A list of existing sessions, each given as a tuple \( (s, e) \) where \( s \) is the start and \( e \) is the end time.
• A list of planned sessions also represented as tuples \( (s, e) \).

You must decide whether it is possible to schedule all sessions (both existing and planned) across the available rooms. If they can be scheduled so that no two sessions in the same room overlap, output yes; otherwise, output no.

Note: When testing, the sessions for each branch are merged together and scheduled using a greedy strategy by sorting them based on start time. If a session can be placed in any room (by checking that the room's last scheduled session ends before the current session starts), it is scheduled in that room.

inputFormat

The input is read from standard input (stdin) and has the following format:

The first line contains an integer T, the number of branches.

For each branch, three lines are provided:

1. A single integer R representing the number of available rooms.
2. A line beginning with an integer N (the number of existing sessions), followed by 2*N integers representing the start and end times of each existing session.
3. A line beginning with an integer M (the number of planned sessions), followed by 2*M integers representing the start and end times of the planned sessions.

All integers are separated by spaces.

outputFormat

For each branch, output a single line containing either "yes" if all sessions can be scheduled without any overlap in any room, or "no" otherwise. The output is written to standard output (stdout).## sample

1
2
2 1 3 4 6
3 0 2 3 5 6 7

yes