IOI Prisoners’ Escape

In the JOI Kingdom, the most secure place is the IOI Prison. The prison consists of \(N\) rooms numbered \(1,2,\dots,N\) and \(N-1\) bidirectional corridors connecting them. For each \(i\) with \(1\le i\le N-1\), the corridor connects room \(A_i\) and room \(B_i\). It is guaranteed that any room is reachable from any other room.

There are \(M\) prisoners numbered \(1,2,\dots,M\). The \(j\)-th prisoner has his bedroom in room \(S_j\) and his workroom in room \(T_j\) (\(1\le j\le M\)). Note that a prisoner may work in a room that is another prisoner’s bedroom. However, each room can serve as at most one prisoner’s bedroom and one prisoner’s workroom.

One morning, all \(M\) prisoners must move from their bedrooms to their workrooms along the shortest path (which is unique since the rooms form a tree). The prison director gives a sequence of instructions of the following form:

• Instruction: Choose a prisoner and move him from his current room to an adjacent room (i.e. a room directly connected by a corridor). To avoid any prisoner communication, a prisoner is never allowed to move into a room that is currently occupied by another prisoner.

In order for the prisoners to start work as early as possible, Mr. APIO (the prison director) wants to know whether there exists a sequence of such instructions that moves every prisoner from his bedroom to his workroom along the shortest path.

Note: On a tree, if there is at least one empty room (i.e. \(N > M\)), then it is always possible to rearrange the prisoners through the empty room(s). When \(N = M\) (i.e. every room is occupied initially), the prisoners can only remain stationary if their bedroom and workroom are the same. Otherwise, rearrangement is impossible.

inputFormat

The input begins with a line containing two integers \(N\) and \(M\) separated by a space.

Then follow \(N-1\) lines, each containing two integers \(A_i\) and \(B_i\) representing a corridor between room \(A_i\) and room \(B_i\) (\(1 \le i \le N-1\)).

Then follow \(M\) lines, each containing two integers \(S_j\) and \(T_j\) representing the bedroom and workroom of the \(j\)-th prisoner (\(1 \le j \le M\)).

outputFormat

Output a single line containing Yes if there exists a valid sequence of moves according to the rules that moves every prisoner along a shortest path from his bedroom to his workroom. Otherwise, output No.

Explanation:

• If \(N > M\), then there is at least one room initially empty, allowing the prisoners to rearrange themselves without conflicts.
• If \(N = M\), every room is occupied initially. In this case, a valid rearrangement exists only if every prisoner is already at his workroom (i.e. \(S_j = T_j\) for all \(j\)); otherwise, the prisoners would block each other.

sample

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

Yes