Informatica Online Judge

  족보찾기 [2136 / 0858]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 10   Total Tried : 13


The Champion of this Problem (C++) : gs16109 - 77ms / 964byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]
Writer ID : [gs16028]

Background

상민이는 자신의 성씨에 굉장한 자부심을 느끼고 있다.

자신과 같은 성을 가진 사람을 매우 친절하게 대해준다.

상민이는 같은 성씨인 승민이를 보고 문득 공통조상이 얼마나 있는지 궁금해졌다. 상민이는 집으로 돌아가 족보를 찾아보았지만 오래된 족보라 페이지가 뒤죽박죽 섞여 있었다.

한 페이지마다 아버지와 아들의 관계만 알아볼 수 있었다. 상민이를 도와주자

Input

족보에 나와있는 사람의 수 N(1<=N<=500000)와 정수 M(M
이후 M개의 줄에 두 번호 X와 Y가 주어진다. X는 Y의 아버지이다.

쿼리의 개수 Q(1<=Q<=100)이 주어진다.

이후 Q개의 줄에 조상의 수를 비교할 A와 B가 주어진다.

Output

Q개의 줄에 A와 B의 공통조상의 수를 출력한다.

만약 A와 B의 공통조상이 없다면 -1을 출력한다.

IO Example

입력
3 2
1 2
2 3
1
2 3

출력
2

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]