마트료시카 박스 III

ChAOS 회사는 마트료시카 박스를 만드는 것으로 유명한 회사이다. 마트료시카 박스 안에는 또 다른 마트료시카 박스를 넣을 수 있다. 따라서 마트료시카 박스는 박스가 여러 겹으로 중첩되어 들어 있는 박스를 뜻한다.

푸앙이는 ChAOS 회사에 마트료시카 박스 주문 제작을 신청하려고 한다. 신청하려면 박스 번호가 중복되지 않은 마트료시카 박스 설계도를 만들어 제출해야 한다. 설계도의 박스 번호는 모두 자연수이며, 메인 박스는 정확히 1개만 있다. 메인 박스는 다른 어떤 박스에도 담기지 않은 박스이다. 푸앙이는 N개의 박스로 구성된 설계도를 만든다.

<표 1>

<그림 1>

<표 1>은 푸앙이가 작성한 마트료시카 박스 설계도 예시이고, <그림 1>은 <표 1>의 설계도를 바탕으로 만든 박스의 모습이다. <그림 1>의 모든 박스는 열려 있다.

서브 박스는 박스를 열었을 때 그 안에 있는 박스 중 열지 않고도 볼 수 있는 박스를 뜻한다.

그런데 ChAOS 회사로부터 제작 공정상 설계도를 고쳐야 한다는 연락을 받았다. 박스마다 서브 박스를 최대 M개까지만 넣을 수 있다는 내용이었다. 난감해진 푸앙이가 당신에게 도움을 요청하였다.

설계도를 수정하는 과정에서 기존 박스의 위치를 옮기거나 새로운 박스를 추가할 수 있다. 새 박스는 푸앙이의 자금 문제로 최대 K개까지만 추가할 수 있다. 추가하는 박스의 번호는 기존 박스 번호와 겹치면 안 된다. 박스의 위치를 옮기는 데는 제약이 없지만, 푸앙이의 부탁에 따라 수정 후 설계도는 수정 전 설계도의 박스 포함 관계를 반드시 유지해야 한다.

$(i,\,j)$ 쌍은 $i$번 박스가 $j$번 박스를 담고 있음을 뜻한다. 수정 전 설계도에서 성립하는 모든 $(i,\,j)$ 쌍의 집합을 $A$, 수정 후 설계도에서 성립하는 모든 $(i,\,j)$ 쌍의 집합을 $B$라고 하자. 이때 $A \subset B$이면 박스 포함 관계가 유지된 것이다.

<표 2>

<그림 2>

<표 2>는 $N = 5,\, M = 2,\, K = 2$일 때의 수정 전 설계도이고, <그림 2>는 <표 2>의 설계도를 바탕으로 만든 박스의 모습이다. <그림 2>의 박스는 모두 열려 있다.

당신은 <표 2>의 설계도에 6번, 7번 박스를 새로 추가하여 모든 박스의 서브 박스가 2개 이하가 되도록 설계도를 수정할 수 있다.

<표 3>

<그림 3>

<표 3>은 <표 2>의 수정 후 설계도이고, <그림 3>은 <표 3>의 설계도를 바탕으로 만든 박스의 모습이다. <그림 3>의 박스는 모두 열려 있다.

1번 박스는 수정 전, 수정 후 모두 2, 3, 4, 5번 박스를 담고 있어 박스 포함 관계가 유지되었다.

당신은 박스 N개로 구성된 수정 전 설계도와 박스 N + S개로 구성된 수정 후 설계도를 받았을 때, 수정 후 설계도가 올바른지 판별하는 프로그램을 작성해야 한다. 새 박스를 최대 K개 추가했고, 각 박스의 서브 박스가 M개 이하이며, 박스 포함 관계가 유지되었다면 올바른 수정 후 설계도이다.

첫 번째 줄에 수정 전 설계도의 박스 개수 N, 수정 후 설계도의 서브 박스 최대 개수 M, 추가할 수 있는 박스 개수 K, 수정 후 설계도에서 추가한 박스 개수 S가 공백으로 구분되어 주어진다. ($3 \leq N \leq 300\,000$; $1 \leq M \leq N - 2$; $0 \leq K,S \leq 300\,000$)

두 번째 줄부터 N개의 줄에 걸쳐 수정 전 설계도가 주어진다. i번째 줄에는 C와 i - 1번 박스에 담긴 서브 박스 번호 C개가 공백으로 구분되어 주어진다. ($2 \leq i \leq N + 1$)

수정 전 설계도에서 주어지는 박스 번호는 모두 N 이하의 자연수이다. 수정 전 설계도에는 서브 박스 개수가 M개보다 많은 박스가 항상 존재한다.

N + 2번째 줄부터 N + S개의 줄에 걸쳐 수정 후 설계도가 주어진다. 수정 후 설계도는 수정 전 설계도와 같은 형식으로 주어진다. 수정 후 설계도에서 주어지는 박스 번호는 모두 N + S 이하의 자연수이다.

수정 후 설계도가 올바르지 않으면 0을 출력한다.

수정 후 설계도가 올바르면 1을 출력한다.