|
|
1 #include <iostream>
2#include <cstdio>
3#include <cstring>
4#include <vector>
5using namespace std;
6
7const int N = 10000;
8vector<int> a[N];
9int f[N], r[N];
10
11  void DFS(int u, int dep) {
12 r[u] = dep;
13  for(vector<int>::iterator it = a[u].begin(); it != a[u].end(); ++it){
14 DFS(*it, dep+1);
15 }
16 }
17
18int main()
19{
20 int casenum, x, y;
21 int n;
22 scanf("%d", &casenum);
23 for(int num = 0; num < casenum; num++){
24 scanf("%d", &n);
25 for(int j = 0; j < n; j++){
26 a[j].clear();
27 }
28 memset(f, -1, sizeof(f));
29 for(int i = 0; i < n-1; i++){
30 scanf("%d%d", &x, &y);
31 a[x-1].push_back(y-1);
32 f[y-1] = x-1;
33 }
34 int i;
35 for( i = 0; f[i] >= 0; i++){
36 ;
37 }
38 cout << i << endl;
39 DFS(i, 0);
40 scanf("%d%d", &x, &y);
41 x--; y--;
42 while(x != y){
43 if(r[x] > r[y]){
44 x = f[x];
45 }
46 else{
47 y = f[y];
48 }
49 }
50 printf("%d\n", x+1);
51 }
52 return 0;
53}
|