문제

번부터 번까지 명의 사람들이 시각 에서 까지 진행되는 회의에 참석한다. 번 사람은 시각 에 와서 에 떠난다. 서로 다른 번 사람과 번 사람이 서로 친하면 두 사람이 회의에 참석하는 동안 즐거운 대화를 나눌 수 있다.

사람들이 회의를 오고 떠나는 시각과 어떤 사람들이 서로 친한지 주어진다. 각 시각 , , , 에 즐거운 대화를 나누고 있는 사람들이 총 몇 쌍 있는지 구하여라.

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

입력

첫 번째 줄에 사람들의 수 과 어떤 사람들이 서로 친한지에 대한 정보 수 , 회의가 끝나는 시각 가 공백으로 구분되어 주어진다.

두 번째 줄부터 개의 줄에 걸쳐 각 사람이 회의를 오고 떠나는 시각이 주어진다. 그중 번째 줄에는 번 사람이 회의를 오는 시각과 떠나는 시각을 나타내는 정수 와 가 공백으로 구분되어 주어진다.

그다음 줄부터 개의 줄에 걸쳐, 각 줄에 서로 친한 두 사람의 번호 와 가 공백으로 구분되어 주어진다.

같은 정보 가 두 번 이상 주어지지 않는다.

출력

각 시각 , , , 에 즐거운 대화를 나누고 있는 사람들이 몇 쌍인지 한 줄에 하나씩 출력한다.