좋은 케이블 관리

시간 제한: 5000 ms. 메모리 제한: 512 MB.

클라라는 케이블이 심하게 엉켜 버렸다. 케이블과 스위치박스를 대량으로 싸게 샀는데, 그때부터 문제가 시작되었다. 각 스위치박스에는 들어오는 커넥터와 나가는 커넥터가 있다. 케이블은 한 스위치박스의 나가는 커넥터와 다른 스위치박스의 들어오는 커넥터를 잇는다. 통신은 한 방향으로만 된다. 신호는 스위치박스의 나가는 커넥터에서 출발해 케이블을 지나, 상대 스위치박스의 들어오는 커넥터로 들어간다.

처음에 클라라의 네트워크는 스위치박스 하나뿐이다. 이후 클라라는 케이블과 스위치박스를 추가하는 두 종류의 업그레이드로 네트워크를 늘렸다.

• 길이 업그레이드(스위치박스 x): 기존 스위치박스 x를 고른다. x의 나가는 케이블을 모두 뽑아 새 스위치박스 y의 나가는 커넥터에 다시 꽂는다. 그다음 x의 나가는 커넥터에서 y의 들어오는 커넥터로 새 케이블을 잇는다.

• 병렬 업그레이드(스위치박스 x): 새 스위치박스 y를 놓고 기존 스위치박스 x를 복제한다. x에 연결된 상대(들어오는 쪽이든 나가는 쪽이든)가 있으면 y도 그 상대와 연결한다. x와 y 사이에는 케이블을 잇지 않는다.

네트워크가 너무 커져서 어느 스위치박스끼리 통신할 수 있는지 알아보기 어려워졌다. 두 스위치박스는 한쪽에서 다른 쪽으로 가는 방향 경로가 있으면 통신할 수 있다. 어느 방향이든 상관없다. 클라라를 도와 질의한 두 스위치박스가 통신할 수 있는 질의의 개수를 세어 보자.

첫 줄에 업그레이드 개수 $N$($1 \le N \le 200\,000$)과 질의 개수 $Q$($1 \le Q \le 200\,000$)가 공백으로 구분되어 주어진다.

다음 $N$개 줄에는 업그레이드가 한 줄에 하나씩 주어진다. 각 줄은 길이 업그레이드를 뜻하는 L 또는 병렬 업그레이드를 뜻하는 P로 시작하고, 이어서 업그레이드할 스위치박스 번호 $x$($1 \le x \le N$)가 나온다. 스위치박스 $x$는 업그레이드하기 전에 이미 네트워크에 있었다. 새로 추가되는 스위치박스 번호 $y$는 아직 쓰이지 않은 가장 작은 양의 정수이므로 항상 $x < y$이다. 처음 스위치박스 번호는 1이다.

다음 $Q$개 줄에는 질의의 두 스위치박스 번호 $u$, $v$($1 \le u < v \le N + 1$)가 한 줄에 하나씩 주어진다.

통신할 수 있는 두 스위치박스를 가진 질의의 개수를 출력한다.

왼쪽 그림은 입력 예제 1의 업그레이드를 적용한 결과 네트워크이다. 오른쪽 그림은 입력 예제 2의 결과를 보여준다.