27238번 - 편지 배달 2

Hello 고등학교에서는 다른 반에 있는 친구와 편지를 주고받는 것이 유행이다. Hello 고등학교에는 $1$반부터 $N$반까지 총 $N$개의 반이 있고, 각 반의 교실은 반 번호 순서대로 직선 형태의 복도를 따라 나열되어 있다.

쉬는 시간마다 복도를 산책하는 것을 좋아하는 동규는, 산책하는 김에 학생들의 편지도 배달해 주기로 했다. 동규가 산책하는 방법은 다음과 같다. 먼저 동규는 $L+1$개의 반 번호 $c_0,c_1,\dots ,c_{L-1},c_L$을 정한다. 이때 $c_0=c_L$은 동규의 반 번호로, 동규는 이곳에서 출발해서 이곳으로 도착해야 한다. 산책은 총 $L$번의 이동으로 이루어진다. $i$번째 이동에서는 현재 위치에서 $c_i$반을 향해 일직선으로 이동한다. 교실이 직선 형태의 복도를 따라 나열되어 있기 때문에, 동규가 $c_{i-1}$반에서 $c_i$반을 향해 이동하는 동안 두 반 사이에 있는 모든 반을 지나게 된다.

학생들은 두 명씩 쌍을 이뤄 편지를 주고받는다. 편지를 주고받을 두 학생은 서로 다른 반에 있어야 한다. $a$반 학생 A와 $b$반 학생 B가 편지를 주고받는 방법은 다음과 같다.

• 먼저 A가 B에게 보낼 편지를 준비한다. 동규는 산책 도중 처음으로 $a$반을 지날 때 A의 편지를 건네받는다.
• 동규는 A의 편지를 받은 이후 처음으로 $b$반을 지날 때 B에게 편지를 전달하고, B는 편지를 받은 즉시 답장 편지를 작성해서 동규에게 건넨다.
• 동규는 B의 편지를 받은 이후 처음으로 $a$반을 지날 때 A에게 편지를 전달하고, A는 편지를 받은 즉시 답장 편지를 작성해서 동규에게 건넨다.
• 동규가 산책을 끝낼 때까지 두 학생은 계속 번갈아서 답장 편지를 보낸다.

총 $M$쌍의 학생들이 편지를 주고받고자 한다. 동규는 편지를 동시에 몇 개든지 지닐 수 있으며, 산책을 시작할 때와 끝낼 때에도 자기 반에서 편지를 건네받거나 전달할 수 있다. 산책이 끝났을 때 동규에게 남은 편지는 배달하지 못한 것으로 간주한다. $i=1,\dots ,L$에 대해, 동규가 $i$번째 이동을 마쳤을 때 지금까지 전달한 편지의 개수를 구하시오.

첫 번째 줄에 정수 $N,L,M$이 공백으로 구분되어 주어진다.

두 번째 줄에 동규의 산책 경로를 나타내는 $L$개의 정수 $c_0,\dots ,c_{L-1}$이 공백으로 구분되어 주어진다. $c_L$은 $c_0$과 같으므로 주어지지 않음에 유의하라.

세 번째 줄부터 $M$개의 줄에, 편지를 주고받을 학생 쌍에 대한 정보 $a,b$가 공백으로 구분되어 주어진다. $a$반과 $b$반에 있는 학생이 서로 편지를 주고받고자 함을 나타내며, $a$반의 학생이 먼저 편지를 보낸다.

총 $L$개의 줄을 출력한다. $i$번째 줄에는 동규가 $i$번째 이동을 마쳤을 때 지금까지 배달한 편지의 개수를 출력한다.

• $2\le N\le 200\ 000$
• $1\le L,M\le 200\ 000$
• $1\le c_i\le N$
• 모든 학생 쌍에 대해서, $1\le a,b\le N$이고 $a\ne b$를 만족한다.