박스와 화살표 다이어그램

정말 창피한 일이다. Itaf는 지난 'Fundamental programming in Python' 시험에서 0/5점을 받았다. 그녀는 KTH에서 공학물리학을 전공하며 이 과목에 어려움을 겪고 있다. 올해 반 학생의 $60\%$가 시험에서 떨어졌으니 그녀만 그런 것도 아니다. 이렇게 높은 비율의 원인은 이른바 box and arrow diagram(låd- och pildiagram)이다.

box and arrow diagram의 예시이며, github.com/dicander/box_arrow_diagram에서 가져왔다.

이 시험 문제에서는 파이썬 코드가 주어지고, 프로그램이 특정 줄에 도달했을 때의 메모리 구조를 그려야 한다. Itaf는 경쟁 프로그래밍 실력이 뛰어나지만, 주제가 '너무 쉽다'고 느껴져 공부를 자꾸 미뤘다. 이제 그녀는 절박하게 도움을 청하고 있다.

box and arrow diagram은 파이썬의 메모리 구조를 설명하는 데 쓰는 도구이다. 단순하게 보면, 이 다이어그램은 1부터 N까지 번호가 붙은 노드(상자)와 1부터 M까지 번호가 붙은 간선(화살표)으로 이루어진 방향 그래프이다. 상자는 파이썬 프로그램 메모리 속 객체에 대응한다. 상자 1은 특별하며 전역(global) 객체를 나타낸다. 상자 u에서 상자 v로 화살표가 그려져 있으면, 객체 u가 객체 v를 가리키는 참조를 저장하고 있다는 뜻이다. u가 v를 가리키는 참조를 여러 개 저장하면 u에서 v로 화살표를 여러 개 그린다. 객체가 자기 자신을 참조하는 것도 가능하다.

객체 u는 다이어그램에서 전역 객체부터 u까지 이어지는 경로가 존재하면 살아 있다고 한다. 각 객체에는 참조 카운터도 있다. 객체 u의 참조 카운터는 살아 있는 객체 v에서 u로 향하는 화살표 (v, u)의 개수이다.

Itaf를 도와 Q개의 질의에 답하라. 질의는 다음 두 종류 중 하나이다.

• 1 X: 번호가 X인 화살표를 다이어그램에서 제거한다.
• 2 Y: 번호가 Y인 객체의 참조 카운터를 출력한다.

첫 줄에는 공백으로 구분된 두 정수 N과 M이 주어진다($1 \leq N, M \leq 2 \times 10^5$). N은 상자의 개수이고 M은 화살표의 개수이다.

다음 M개의 줄에서 i번째 줄에는 공백으로 구분된 두 정수 U_i와 V_i($1 \leq U_i, V_i \leq N$)가 주어진다. 이는 번호가 i인 화살표가 상자 U_i에서 상자 V_i로 향한다는 뜻이다. 고리와 다중 간선이 허용된다.

다음 줄에는 질의의 개수 Q($1 \leq Q \leq 2 \times 10^5$)가 주어진다. 다음 Q개의 줄에서 j번째 줄에는 공백으로 구분된 두 정수 C_j와 X_j가 주어진다($1 \leq C_j \leq 2$).

• C_j = 1이면 번호가 X_j인 화살표를 제거한다($1 \leq X_j \leq M$).
• C_j = 2이면 객체 X_j의 참조 카운터를 출력한다($1 \leq X_j \leq N$).

같은 번호의 화살표를 두 번 제거하는 종류 1 질의는 주어지지 않는다.

종류 2 질의마다 객체 Y_j의 참조 카운터를 한 줄에 출력한다.