Extra
Time
树的问题 Time:1s Memory:50M AC:0% Submit:2

描述

    有一个由n个点构成的无根树,把这n个点分别作为根节点,我们可以造出n个有根树。有若干询问,每次询问是两个点a和b(a≠b),我们想知道在这n个有根树中,有多少个树满足a是b的祖先或者b是a的祖先。

输入格式

    输入有n+q行,第一行有两个用空格隔开的正整数n和q,q表示询问数,接下来的n-1行,每一行有两个用空格隔开的正整数,分别表示一条边所连的两个点。接下来的q行,每行是一组询问。输入保证能构成一棵树。

输出格式

 输出有q行,对应每组询问。

样例输入

 4 3

 1 2

 2 3

 3 4

 1 4

 2 3

 1 3

样例输出

 2

 4

 3

数据范围与约定

    30%的数据,0<n≤100,0<q≤100。

    60%的数据,0<n≤1000,0<q≤1000。

100%的数据,0<n≤200000,0<q≤200000。