Rooted Tree Validity Under Edge Reversals

You are given a tree with \( n \) nodes and \( n-1 \) directed edges representing parent-child relationships. It is guaranteed that initially, the given graph is a rooted tree. Then, you are given \( m \) modifications. In each modification, you are provided a pair of nodes \( (u, v) \) corresponding to a parent-child relationship in the current graph. You must reverse the edge between \( u \) and \( v \) (i.e. the parent becomes the child and the child becomes the parent).

Your task is to determine, before any modifications and after each modification, whether the resulting graph is a rooted tree.

A directed graph is a rooted tree if it satisfies the following conditions:

• There is exactly one node (the root) with indegree 0, and every other node has indegree exactly 1.
• The graph is acyclic, and all nodes are reachable from the root.

Note: In each modification, the provided pair \( (u, v) \) is guaranteed to exist in one direction in the current graph. Reverse the edge accordingly.

inputFormat

The input is given in the following format:

 n m
 u1 v1
 u2 v2
 ...
 u(n-1) v(n-1)
 mod1_u mod1_v
 mod2_u mod2_v
 ...
 modm_u modm_v

Here, \( n \) is the number of nodes, \( m \) is the number of modifications, the next \( n-1 \) lines represent the initial parent-child relationships, and the following \( m \) lines each represent a modification. All node labels are assumed to be 1-indexed.

outputFormat

Output \( m+1 \) lines. The first line corresponds to the original tree and should be either YES or NO depending on whether the initial graph is a rooted tree. Each of the following \( m \) lines corresponds to the graph after applying each modification in order, outputting YES if the resulting graph is a rooted tree, or NO otherwise.

sample

3 1
1 2
1 3
1 2

YES
YES