시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 112 53 44 51.765%

문제

상도는 N개의 스위치와 M개의 램프를 갖고 있다. 스위치는 램프의 전원을 켤 수 있다. 스위치와 연결된 램프의 개수는 0개 이상이다.

가장 처음에 램프는 모두 꺼져 있다.

스위치를 누르면 램프의 전원이 켜진다. 스위치를 이용해서 램프의 전원을 끌 수는 없다. 예를 들어, 한 램프에 두 스위치가 연결되어 있는 경우에 한 스위치를 누르거나, 두 스위치를 모두 누르면 램프는 켜져 있는 상태가 된다.

N개의 스위치를 모두 누르면 모든 램프가 켜진다. 상도는 N-1개의 스위치를 눌러도 모든 램프가 켜지는지 궁금해졌다. 

스위치와 램프의 연결 상태가 입력으로 주어진다. N-1개의 스위치를 눌러서 모든 램프를 켤 수 있는지 알아보자.

입력

첫째 줄에 스위치의 수 N, 램프의 수 M이 주어진다. 둘째 줄부터 N개의 줄에는 스위치에 대한 정보가 주어진다. 스위치 정보의 첫 번째 정수는 그 스위치와 연결된 램프의 수이고, 이후 연결된 램프의 번호가 공백으로 구분되어져 있다.

스위치와 램프의 번호는 1번부터 시작한다.

N개의 스위치를 모두 누르면 모든 램프가 켜지는 입력만 주어진다.

출력

N-1개의 스위치를 눌러서 모든 램프를 켤 수 있으면 1을, 없으면 0을 출력한다.

제한

  • 1 ≤ N, M ≤ 2,000

예제 입력 1

4 5
3 1 3 5
1 2
3 3 4 5
1 1

예제 출력 1

1

예제 입력 2

4 5
2 1 3
1 2
2 3 4
2 3 5

예제 출력 2

0

예제 입력 3

10 1
1 1
0
0
0
0
0
0
0
0
1 1

예제 출력 3

1

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013