31997번 - 즐거운 회의

문제

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$에 즐거운 대화를 나누고 있는 사람들이 몇 쌍인지 한 줄에 하나씩 출력한다.

제한

노트