시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 (추가 시간 없음) 1024 MB 363 165 140 49.296%

문제

2020년, 신종 전염병이 유행하여 UCPC국 질병관리본부에서 역학 조사를 하고 있다. UCPC국의 인구는 총 $N$명이며 각각 $1$, $2$, $\cdots$, $N$번의 주민번호가 붙어있다.

질병관리본부는 지금까지 $M$개의 모임이 있었다는 사실을 파악했다. 각 모임은 $k$명이 참여했고 해당 모임은 주민번호가 $a_1, a_2, \cdots, a_k$인 사람들이 참여했다.

전염병은 밀접하고 밀폐된 공간에서만 전염되기 때문에 반드시 모임 안에서만 전염된다. 전염병이 전파되는 규칙은 다음과 같다.

  • 모임에 참여한 사람들 중 한 명 이상의 사람이 전염병에 감염되어 있었다면 모임에 참여한 모든 사람들이 전염병에 감염된다.
  • 모임에 전염병에 감염된 사람이 없다면 아무 일도 일어나지 않는다.

질병관리본부는 확보한 자료를 가지고 초기 감염자들을 예측하려고 한다. 모임의 정보 및 $M$개의 모임이 끝나고 나서 전염병에 감염된 사람의 정보가 주어지면 첫 번째 모임을 하기 전에 감염되어 있던 사람을 역추적하는 프로그램을 작성하여라. 위 규칙 이외의 경로로 전염병이 전파되거나 전염병이 치료되는 경우는 없다고 간주한다.

입력

첫 번째 줄에 사람의 수 $N$, 모임의 수 $M$ ($2 \le N \le 100\ 000$, $1 \le M \le 100\ 000$)이 주어진다.

두 번째 줄부터 $M$개의 줄에는 모임의 정보가 시간 순으로 주어진다. 각 줄에는 각 모임에 참여하는 사람의 수 $k$ ($2 \le k \le N$)와 모임에 참여한 사람의 주민번호 $a_i$ ($1 \le a_i \le N$, $a_i \ne a_j$)가 주어진다. 여러 모임이 동시에 진행되는 경우는 없다.

마지막 줄에는 $N$명의 사람들에 대한 감염 정보가 주어진다. 마지막 모임이 끝나고 주민번호가 $i$인 사람이 전염병에 감염되었다면 1을, 그렇지 않다면 0이 주어진다. 감염된 사람이 없을 수 있음에 유의하여라.

$k$들의 합은 $1\ 000\ 000$을 넘지 않는다.

출력

만약 모임을 하기 전에 감염된 사람을 역추적할 수 없다면 NO를 출력한다.

그렇지 않다면 첫 번째 줄에 YES를 출력하고 두 번째 줄에 감염 정보를 의미하는 정수 $N$개를 공백으로 구분하여 출력한다. 이 중 $i$번째 수는 주민번호가 $i$인 사람이 첫 번째 모임이 시작되기 전에 전염병에 감염되어 있었으면 1이며, 아니면 0이다. 가능한 감염 상태가 여러 개이면, 그중 아무 것이나 출력하면 된다.

예제 입력 1

7 3
3 1 2 3
3 3 4 5
3 5 6 7
0 0 1 1 1 1 1

예제 출력 1

YES
0 0 0 1 1 1 1

예제 입력 2

7 3
3 1 2 3
3 3 4 5
3 5 6 7
1 0 1 0 1 0 1

예제 출력 2

NO