[Solution] Escape The Maze (easy version) solution codeforces

Escape The Maze (easy version) solution codeforces

Vlad built a maze out of 𝑛n rooms and 𝑛1n−1 bidirectional corridors. From any room 𝑢u any other room 𝑣v can be reached through a sequence of corridors. Thus, the room system forms an undirected tree.

Vlad invited 𝑘k friends to play a game with them.

Vlad starts the game in the room 11 and wins if he reaches a room other than 11, into which exactly one corridor leads.

Friends are placed in the maze: the friend with number 𝑖i is in the room 𝑥𝑖xi, and no two friends are in the same room (that is, 𝑥𝑖𝑥𝑗xi≠xj for all 𝑖𝑗i≠j). Friends win if one of them meets Vlad in any room or corridor before he wins.

For one unit of time, each participant of the game can go through one corridor. All participants move at the same time. Participants may not move. Each room can fit all participants at the same time.

Also read: ATM and Students solution codeforces

Friends know the plan of a maze and intend to win. Vlad is a bit afraid of their ardor. Determine if he can guarantee victory (i.e. can he win in any way friends play).

In other words, determine if there is such a sequence of Vlad’s moves that lets Vlad win in any way friends play.

Escape The Maze (easy version) solution codeforces Input

The first line of the input contains an integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases in the input. The input contains an empty string before each test case.

The first line of the test case contains two numbers 𝑛n and 𝑘k (1𝑘<𝑛21051≤k<n≤2⋅105) — the number of rooms and friends, respectively.

The next line of the test case contains 𝑘k integers 𝑥1,𝑥2,,𝑥𝑘x1,x2,…,xk (2𝑥𝑖𝑛2≤xi≤n) — numbers of rooms with friends. All 𝑥𝑖xi are different.

The next 𝑛1n−1 lines contain descriptions of the corridors, two numbers per line 𝑣𝑗vj and 𝑢𝑗uj (1𝑢𝑗,𝑣𝑗𝑛1≤uj,vj≤n) — numbers of rooms that connect the 𝑗j corridor. All corridors are bidirectional. From any room, you can go to any other by moving along the corridors.

Also read: Make Even solution codeforces

It is guaranteed that the sum of the values 𝑛n over all test cases in the test is not greater than 21052⋅105.

Output Escape The Maze (easy version) solution codeforces

Print 𝑡t lines, each line containing the answer to the corresponding test case. The answer to a test case should be “YES” if Vlad can guarantee himself a victory and “NO” otherwise.

You may print every letter in any case you want (so, for example, the strings “yEs“, “yes“, “Yes” and “YES” will all be recognized as positive answers).

Example Escape The Maze (easy version) solution codeforces

input

Copy
4

8 2
5 3
4 7
2 5
1 6
3 6
7 2
1 7
6 8

3 1
2
1 2
2 3

3 1
2
1 2
1 3

3 2
2 3
3 1
1 2

output

Copy
YES
NO
YES
NO
Note Escape The Maze (easy version) solution codeforces

In the first test case, regardless of the strategy of his friends, Vlad can win by going to room 44. The game may look like this:

The original locations of Vlad and friends. Vlad is marked in green, friends — in red.
Locations after one unit of time.
End of the game.
Note that if Vlad tries to reach the exit at the room 88, then a friend from the 33 room will be able to catch him.

Escape The Maze (easy version) solution codeforcesMaximum Number of Tasks You Can Assign solution leetcodeMaximum Number of Tasks You Can Assign solution leetcodeMaximum Number of Tasks You Can Assign solution leetcode

Leave a Comment

Your email address will not be published. Required fields are marked *