Informatica Online Judge

  솔로나라 #2 [2376 / 0948]

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


The Champion of this Problem (C++) : gs18113 - ms / 869byte
My Best Submission (C++) : N/A

[36th 성재용(gs18060)]
Writer ID : [gs18060]

Background

명진이는 평화로운 솔로나라에 살고 있다. 이 나라에는 도시들이 있는데, 도시들은 모두 도로로 연결되어 있다. 또한 이 도시들은 트리 모양을 띄고 있다.

명진이는 한 지점에서 자신이 짝사랑하는 승영이가 있는 곳까지 최단 경로로 갈려고 한다. 명진이는 도시 $C$에 있고 승영이는 도시 $D$에 있다.

그런데 명진이가 지나간 도시(시작점과 도착점 포함)들은 사랑해피바이러스에 감염되어 고통스러워 한다. 그래서 솔로인 준서는 명진이가 승영이한테 가려는 것을 알게 되고 피해를 최소화하려고 한다.

그래서 감염된 도시들과 이에 연결된 도로를 제외하면 여러개의 도시들끼리 연결되어있는 고립된 도시들이 만들어지는데, 이를 작은 나라라고 하자. 그러면 준서는 작은 나라들의 크기의 최댓값을 구하려고 한다.

그런데 준서는 명진이와 승영이의 위치를 몰라서 여러번 시뮬레이션을 해보려고 한다. 하지만 준서가 어려워하고 있다. 여러분이 준서를 도와주자.

Input

첫번째 줄에는 도시의 개수 $N (1 \le N \le 10^5)$와 시뮬레이션 횟수 $T (1 \le T \le 10^5)$가 주어진다.
두번째 줄부터 $N$번째 줄까지 도로의 정보가 나타난다. 각 줄에는 두개의 수 $A (1 \le A \le N)$와 $B (1 \le B \le N)$가 공백으로
구분되어 주어진다. $N+1$번쨰 줄부터 $N+T$번쨰 줄 까지는 시뮬레이션을 위한 두개의 수 $C (1 \le C \le N)$와 $D (1 \le D \le N)$가
공백으로 구분되어 주어진다.

17005 공병규 조건 수정

Subtask #1: 각 정점에 연결된 최대 간선의 개수는 2이다.
Subtask #2: $1 \le N \le 5 \times 10^3,\ 1 \le T \le 5 \times 10^3$
Subtask #3: 추가 제약이 없다.

Output

$T$줄에 걸쳐서 각 줄에 수를 한개씩 출력한다. $k$번째 수는 입력의 $N+k$번째줄의 시뮬레이션의 답이다.

IO Example

입력
5 6
3 1
2 5
4 5
3 5
1 3
2 2
2 4
3 4
3 5
2 4

출력
3
4
2
1
1
2

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