즐거운 회의

$1$번부터 $N$번까지 $N$명의 사람들이 시각 $t=0$에서 $t=T$까지 진행되는 회의에 참석한다. $i$번 사람은 시각 $t=a_i$에 와서 $t=b_i$에 떠난다. 서로 다른 $A$번 사람과 $B$번 사람이 서로 친하면, 두 사람이 회의에 참석하는 동안 즐거운 대화를 나눌 수 있다.

사람들이 회의에 오고 떠나는 시각과 어떤 사람들이 서로 친한지가 주어진다. 각 시각 $t=0.5$, $t=1.5$, $\cdots$, $t=T-0.5$에 즐거운 대화를 나누고 있는 사람들이 총 몇 쌍인지 구하여라.

사람들의 쌍을 셀 때 순서는 고려하지 않는다. 즉, $A$번 사람과 $B$번 사람의 쌍은 $B$번 사람과 $A$번 사람의 쌍과 같다.

첫 번째 줄에 사람들의 수 $N$, 친한 관계 정보의 수 $M$, 회의가 끝나는 시각 $T$가 공백으로 구분되어 주어진다. $(2 \le N \le 200\,000$; $1 \le M, T \le 200\,000)$

두 번째 줄부터 $N$개의 줄에 걸쳐 각 사람이 회의에 오고 떠나는 시각이 주어진다. $i$번째 줄에는 $i$번 사람이 회의에 오는 시각 $a_i$와 떠나는 시각 $b_i$가 공백으로 구분되어 주어진다. $(0 \le a_i \lt b_i \le T)$

그다음 $M$개의 줄에 걸쳐 서로 친한 두 사람의 번호 $c$와 $d$가 공백으로 구분되어 주어진다. $(1 \le c \lt d \le N)$

같은 정보 $(c, d)$가 두 번 이상 주어지지 않는다.

각 시각 $t=0.5$, $t=1.5$, $\cdots$, $t=T-0.5$에 즐거운 대화를 나누고 있는 사람들의 쌍이 몇 쌍인지 한 줄에 하나씩 출력한다.