Shika Bika
Time limit2sMemory limit512 MB
Given unordered pairs where one value in each pair lies in an unknown integer range, decide for each query whether it is surely in the range or not sure.
- Level
Medium5 of 10
- Topics
- Math, Implementation
- Solved
- No attempts yet
Problem
Shika and Bika are two cute little sisters. They like to play together all the time. These days, they are learning about integers. They made up the following game. Shika picks an integer range without telling Bika. The game goes in rounds. In each round, Shika calls out one integer from the range, and Bika replies with any integer (the reply does not need to be in the range). Shika ends the game only after she has called out every integer in the range at least once. She may call the same integer more than once, and Bika may reply with a different integer each time. For example, Shika may call out 3 and Bika replies with 4. Later, Shika calls out 3 again and Bika replies with 3. After each round, they write down a pair made of the integer Shika called and the integer Bika replied with.
The write-up has two problems:
- The pair is not written in a fixed order. If Shika calls x and Bika replies with y, they sometimes write (x, y) and other times write (y, x).
- In some rounds, they forget to write the pair at all.
The next day, Shika asks Bika questions like "Did I call out integer q yesterday?" Bika has the write-up and may answer YES, NO, or NOT SURE. Given the written pairs, can you help Bika answer Shika's questions?
Input
The first line contains a single integer T (1 ≤ T ≤ 100), the number of test cases. Each test case starts with a line containing two space-separated integers N and Q (1 ≤ N ≤ 1000, 1 ≤ Q ≤ 1000). The next N lines each contain two space-separated integers a and b (-1,000,000 ≤ a, b ≤ 1,000,000), the i-th written pair. The next Q lines each contain one integer A (-1,000,000 ≤ A ≤ 1,000,000), the j-th query.
Output
For each test case, print Q lines. The i-th line is the answer to the i-th query: YES, NO, or NOT SURE.
Hint
In this test case, these are the possibilities:
- Round 1: Shika calls out 10, Bika replies with 7. Round 2: Shika calls out 20, Bika replies with 14.
- Round 1: Shika calls out 10, Bika replies with 7. Round 2: Shika calls out 14, Bika replies with 20.
- Round 1: Shika calls out 7, Bika replies with 10. Round 2: Shika calls out 20, Bika replies with 14.
- Round 1: Shika calls out 7, Bika replies with 10. Round 2: Shika calls out 14, Bika replies with 20.
For the first query, Bika cannot decide whether Shika called out 3, because some rounds may be missing from the write-up. For the second query, in possibilities 1 and 2, Bika cannot guarantee that Shika called out 8. For the third query, 11 was certainly called out, because it lies between the two integers Shika called in every possibility.