24543번 - 선인장이 무럭무럭 자라고 있어요 스페셜 저지

문제

ICPC Sinchon은 다른 곳에서 볼 수 없는 귀엽고 특별한 선인장을 하나 갖고 있다. 귀엽고 깜찍하고 특별한 이 선인장은 신촌 연합의 지시 하에 선인장을 몹시 무서워하는 국렬이가 어쩔 수 없이 관리하고 있다.

선인장 그래프(cactus graph)는 모든 간선이 최대 한 개의 사이클에 속한 연결된 무방향 그래프다. 즉, 임의의 서로 다른 두 사이클이 최대 하나의 공통 정점을 가지는 무방향 연결 그래프를 의미한다. 국렬이가 관리하는 선인장은 $N$개의 정점과 $M$개의 간선으로 구성된 선인장 그래프로 표현할 수 있다. 그리고 각 정점에 피어나는 꽃의 색깔이 1ドル$번부터 $C$번까지 지정되어있다.

선인장의 줄기는 단순 사이클 하나, 또는 어느 사이클에 속하지 않은 간선 하나를 의미한다. 국렬이는 학기가 시작하는 3월 1일부터 $Q$일 동안 선인장의 어느 줄기에 물을 주는지에 대한 계획을 미리 세웠다. 위의 그림과 같이 국렬이가 특정 줄기에 $x$mL 만큼의 물을 준다면 그 줄기에 속한 정점에 꽃이 각각 $x$개 만큼 피어난다. 그러나 물을 너무 많이 주면 꽃이 건강하게 자라지 않기에 하루에 한 줄기에만 물을 줄 것이다.

신촌 연합 대학교에 속한 각 동아리 회장들이 이 선인장의 소식을 듣고 국렬이에게 찾아와서 선인장의 꽃만 따로 구입하려고 한다. 총 $C$명의 회장이 찾아왔으며 각각 1ドル$번부터 $C$번까지 색깔의 꽃을 구입하려고 한다. $i$번 색깔의 꽃을 구입하려고 하는 회장은 최소 $c_i$개의 꽃을 구입하려고 한다. 따라서 구입 일에는 $i$번 색깔의 꽃이 최소 $c_i$개여야 한다. 국렬이가 물을 주기 시작한지 $Q$일이 지나면 판매되지 않은 선인장의 꽃들은 바로 시들기 때문에 동아리 회장들은 국렬이가 물을 주는 $Q$일 중에 무조건 꽃을 구입해야 한다.

그러나 현재 코로나-19 오미크론 변종 확산 문제가 있을 수 있어서, ICPC Sinchon 측에서는 꽃을 구입하는 사람들이 한꺼번에 오는 걸 원하지 않는다. 따라서, 국렬이는 하루에 한 명에게만 꽃을 판매하려고 한다. 즉, $Q$일 중 $C$명의 회장이 각각 다른 $C$일에 꽃을 구입해야 한다.

신촌 대학교의 동아리 회장들 모두가 원하는 개수의 꽃을 구입할 수 있는지를 판단해보자.

입력

첫 번째 줄에 선인장 그래프의 정점 개수 $N,ドル 간선 개수 $M,ドル 색깔의 개수 $C,ドル 꽃이 피어나는 일 수 $Q$가 주어진다. (2ドル \le N \le 100,000円,ドル 1ドル \le C \le N,ドル $N-1 \le M < 1.5N,ドル 1ドル \le Q \le 200,000円$)

두 번째 줄부터 $M$개의 줄에 걸쳐서 선인장 그래프의 간선 정보가 $N$ 이하의 서로 다른 양의 정수 $p,ドル $q$로 주어진다. 이는 $p$번째 정점과 $q$번째 정점을 잇는 간선이 존재함을 의미한다.

$(M+2)$번째 줄에 각 정점 별로 피어나는 꽃의 색깔에 대한 정보가 $N$개의 $C$ 이하의 양의 정수로 주어진다. 해당 줄의 $i$번째 정수는 $i$번째 정점에 피어나는 꽃의 색깔을 의미한다.

$(M+3)$번째 줄에 각 회장이 구입하고 싶은 꽃의 최소 개수에 대한 정보가 $C$개의 2ドル \cdot 10^{18}$ 이하의 양의 정수로 주어진다. 해당 줄의 $i$번째 정수는 $i$번 색깔의 꽃을 구입하고자 하는 회장이 원하는 최소 꽃의 개수 $c_i$를 의미한다.

$(M+4)$번째 줄부터 $Q$개의 줄에 걸쳐서 물을 주는 것에 대한 정보를 3개의 양의 정수 $u,ドル $v,ドル $k$로 주어진다. 이는 $u$번째 정점과 $v$번째 정점을 잇는 간선이 속한 줄기에 물 $k$mL를 준다는 의미다. (1ドル \le u, v \le n,ドル $u \ne v,ドル 1ドル \le k \le 100,000円$)

출력

신촌 대학교의 동아리 회장 모두가 원하는 개수의 꽃을 구입할 수 있으면 첫 번째 줄에 1을 출력한다. 구입할 수 없다면 -1을 출력한다.

원하는 개수의 꽃을 구입할 수 있다면 각 회장 별로 몇 번째 날에 구입을 해야 하는지 출력한다. 답이 여러 개인 경우, 그중 아무것이나 출력하면 된다.

제한

노트