레이팅 미적용농부 존(Farmer John)에게는 N-1개의 양방향 도로로 연결된 N개 (2 <= N <= 100,000)의 황량한 목초지가 있으며, 임의의 두 목초지 사이에는 정확히 하나의 경로가 존재한다. 풀 뜯는 시간을 사랑하는 소 베시(Bessie)는 목초지 사이의 도로에 풀이 없다고 자주 불평한다. 농부 존은 베시를 몹시 아끼기에, 오늘 드디어 도로에 풀을 심기로 했다. 존은 M개 (1 <= M <= 100,000)의 단계로 이루어진 절차에 따라 풀을 심을 것이다.
각 단계에서는 다음 두 가지 중 하나가 일어난다.
- FJ가 두 목초지를 골라, 두 목초지 사이의 각 도로에 풀을 한 뙈기씩 심는다. 또는,
- 베시가 특정 도로에 풀이 몇 뙈기 있는지 물어보고, 농부 존은 그 질문에 답해야 한다.
농부 존은 수를 세는 데 몹시 서투르다. 베시의 질문에 답하는 것을 도와주자!
첫째 줄: 공백으로 구분된 두 정수 N과 M.
둘째 줄부터 N번째 줄까지: 도로의 양 끝점을 나타내는, 공백으로 구분된 두 정수.
N+1번째 줄부터 N+M번째 줄까지: i+1번째 줄은 단계 i를 설명한다. 줄의 첫 문자는 P 또는 Q로, FJ가 풀을 심는지 아니면 단순히 질의하는지를 나타낸다. 그 뒤에 FJ의 행동 또는 질의를 설명하는, 공백으로 구분된 두 정수 A_i와 B_i (1 <= A_i, B_i <= N)가 이어진다.
첫째 줄부터 ???번째 줄까지: 각 줄에 질의 하나에 대한 답을, 입력에 질의가 나타나는 순서대로 출력한다.
grassplant.in · 출력을 쓸 파일 grassplant.out4 6
1 4
2 4
3 4
P 2 3
P 1 3
Q 3 4
P 1 4
Q 2 4
Q 1 42
1
2riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > December > Gold