Description

陈老师在黑板上画了你有一个n 个点(n -1)条边的简单无向连通图，图的节点编号为1~n。汐汐将把图上的节点编号逐个写下来，生成一个序列p，初始时p为空，然后汐汐执行以下操作n次:

1.选择一个未被删除的点，要求这个点最多只有一条邻边。

2.删去它及它所连接的边，并将它的编号加入到序列p的末尾。

因为每次操作中最多只有一条邻边的点可能有很多个，而汐汐可以任意选择它们之中的一个，所以有多种不同的序列p可以被生成。

现在有 m 次询问，每次询问给出正整数x，y，请你回答汐汐是否可以生成一个p使得px=y，即节点y能否在第x次操作时被选择。

Input Format

第一行两个正整数 n,m。

接下来(n - 1)行，每行两个正整数 u,v。表示图中的一条边。

接下来 m 行，每行两个正整数 x,y，表示一次询问。

Output Format

m行，每行一个字符串，若可行输出 Yes，否则输出 No。

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

Yes  
No  
No  
Yes  
Yes  
Yes  
Yes  
No  
Yes  
Yes  
Yes  
Yes  
Yes  
Yes  
Yes  
Yes  
Yes  
Yes  
Yes  
Yes  
Yes  
Yes  
Yes  
Yes  
Yes

Hint

# 样例解释

以下是所有可以生成的序列p:

1 2 4 3 5

1 2 4 5 3

1 2 5 3 4

1 2 5 4 3

1 4 2 3 5

1 4 2 5 3

1 4 5 2 3

1 4 5 3 2

1 5 2 3 4

1 5 2 4 3

1 5 4 2 3

1 5 4 3 2

4 1 2 3 5

4 1 2 5 3

4 1 5 2 3

4 1 5 3 2

4 5 1 2 3

4 5 1 3 2

4 5 3 1 2

4 5 3 2 1

5 1 2 3 4

5 1 2 4 3

5 1 4 2 3

5 1 4 3 2

5 4 1 2 3

5 4 1 3 2

5 4 3 1 2

5 4 3 2 1

# 数据规模与提示

数据范围

对于 10% 的数据:n,m <=5

对于 30% 的数据:n,m <= 100。

对于 60% 的数据:n,m <= 5000。

对于 100% 的数据:1<=n,m <=500000 , 1≤u,v,x,y≤n。保证图连通、无自环、无重边。

时间限制：2000ms.

内存限制：512MB.

Source

禅城区赛 DFS 大规模数据优化