JOI 나라는 N개의 도시로 이루어져 있다. 각 도시는 1번부터 N번까지 번호가 매겨져 있고, 1번 도시가 수도이다.

이 나라는 철도 회사가 하나이고, 이 회사가 M개의 노선을 운행하고 있다. 이 노선에는 각각 1부터 M까지 번호가 매겨져 있으며, i번째 노선은 도시 Ui와 도시 Vi를 양방향으로 잇는다. 도시와 도시 사이는 철도 이외의 수단으로 이동할 수 없다. 또 어느 도시에서 어느 도시도 철도를 1회 이상 이용해 이동할 수 있다.

현재 모든 노선의 요금은 1달러이다. 철도 회사가 연이은 적자로 파산 직전이기 때문에, 일부 노선의 요금을 4달러로 올리려고 한다. 이들을 한 번에 인상할 경우 반발이 심하기 때문에 1년에 한 노선씩 Q년 동안 인상하려 한다. 다시 말하면, j년 째(1≤j≤Q)에는 Rj(1≤Rj≤M)번째 노선의 요금을 4달러로 올릴 계획이다. 한번 인상된 요금은 계속 유지된다. 같은 노선을 두 번 인상하는 일은 없다.

한편 철도 회사에서는 매년 만족도 조사를 실시한다. 만족도 조사는 매년 말에 실시하므로 j년째 만족도 조사는 노선 Rj의 요금이 인상된 후 실시한다. 만족도 조사에서는 다음 조건이 참인 사람들이 불만족이라고 답한다.

요금 인상 계획 전에 1번 도시로 가는 최소 비용보다, 지금 1번 도시로 가는 최소 비용이 더 비싸다.

여기서 "요금 인상 계획 전"​은 JOI 나라의 첫 요금 인상 전이다.

철도는 환승이 되지 않기 때문에, 어떤 경로의 비용은 그 경로에 있는 노선 요금의 합이다.

1번 도시에 사는 사람은 절대 불만족하지 않는다.

앞으로 Q년 동안 요금 인상 계획이 주어졌을 때, 만족도 조사에서 불만족하는 사람이 있는 도시의 수를 찾는 프로그램을 작성하여라. ​ 

Q개의 줄에 거쳐 출력한다. j번째 줄에는 j년째 만족도 조사에서 불만족한 사람이 있는 도시의 수를 출력한다.

부분 문제 

부분 문제 1 [14점] 다음 조건을 만족한다. N≤100 M≤4,950 Q≤30 

부분 문제 2 [14점] Q≤30 

부분 문제 3 [40점] Q개의 출력하는 수 중 서로 다른 것은 50가지를 넘지 않는다. 

부분 문제 4 [32점] 추가 제한 없음.