#define MAX 15
// #define MAX 10001
#include<stdio.h>
int n; //정점의 수
int m; //간선의 수
int P1, P2; //찾을 사람 //양쪽에서 찾지 않게 그냥 하는게 나을듯
int left[MAX];
int right[MAX];
int parent[MAX];
void input() {
scanf(" %d", &n);//전체 사람수 입력
scanf(" %d", &m);//부모자식관계 개수 입력
scanf(" %d %d", &P1, &P2);//촌수 계산 할 사람입력
for (int i = 1; i <= m; i++)
{
int par, chi;
scanf("%d %d", &par, &chi);
parent[chi] = par;
if (left[par] == 0)
{//왼쪽배열이 0이면 -> 비어있으면 넣기
left[par] = chi;
}
else if (left[par] != 0)
{//왼쪽배열이 비어있지 않으면
right[par] = chi;
}
}
}
void init()
{
for (int i = 0; i <= n; i++)
{
left[i] = right[i] = parent[i] = 0;
}
}
int findlen(int root)
{
int cnt = 0;
int FL[10001];
int head = -1;
int tail = -1;
int temp = 0;
FL[++tail] = root;
while (head != tail)
{
temp = FL[++head];
cnt++;
if (left[temp] != 0)
{
{
FL[++tail] = left[temp];
}
if (right[temp] != 0)
{
FL[++tail] = right[temp];
}
}
}
return cnt;
}
int main() {
freopen("input.txt", "r", stdin);
int TC;
scanf(" %d", &TC);
for (int T = 1; T <= TC; T++)
{
init();
input();
int path1[10001];
int path2[10001];
path1[0] = P1;
path2[0] = P2;
parent[1] = 0;
for (int i = 0; path1[i] != 0; i++)
{
path1[i + 1] = parent[path1[i]];
}
for (int i = 0; path2[i] != 0; i++)
{
path2[i + 1] = parent[path2[i]];
}
int root = -1;
for (int i = 0; path1[i] != 0; i++) {
for (int j = 0; path2[j] != 0; j++)
if (path1[i] == path2[j]) {
root = path1[i]; //root찾고 일단 나오기
break;
}
if (root != -1) break;
}
int len = 0;
len = findlen(root);
printf("#%d %d %d\n", T, root, len);
}
return 0;
}
댓글