JOI국에는 1 에서 N 까지 번호가 매겨진 N 개의 도시와 1 에서 M 까지 번호가 매겨진 M 개의 도로가 있습니다. 도로 i ( 1 ≤ i ≤ M )는 도시 U_i 와 도시 V_i를 양방향으로 연결합니다.

JOI국은 1 에서 K 까지 번호가 매겨진 K 개의 주로 구성됩니다. 도시 j ( 1≤j≤N )는 주 S_j에 속한다. 또한 모든 주에는 적어도 하나 의 도시가 포함됩니다.

JOI국의 산업 장관인 K 이사장은 앞으로 Q 회의 교역을 하고 싶다고 생각하고 있다. k 번째 교역 ( 1≤k≤Q )은 도시 A_k 에서 도시 B_k 로 여러 도로와 도시를 통해 특산품을 운송 합니다 . 다만, 이 교역에 협력해 주는 것은 주 S_{A_k}와 주 S_{A_k}만 (S_{A_k} = S_{B_k}인 경우는 주 S_{A_k}만)이며, 이러한 주에 속하지 않은 도시를 지나가면 특산품은 도난당해 버린다.

K 이사장은 특산품이 도난당하지 않도록 교역을 하는 운송 경로가 있는지 조사하고 싶다. 도시와 도로의 배치, 주와 교역의 정보가 주어졌을 때, 각 교역에 대해 특산품을 무사히 전달할 수 있는지를 판정하는 프로그램을 작성하라.

#5858 upload 5 done 2 how_to_reg 2 call_split Subtask

교역 계획 (Trade Plan) timer 4s memory 1024MB

#5858
Subtask

교역 계획 (Trade Plan) 4s 1024MB