스위치와 램프

면접 대비

시간 제한2초메모리 제한512 MB

요약

모든 램프를 켜는 N개의 스위치 연결 정보가 주어질 때, 스위치 하나를 빼고 눌러도 모든 램프를 켤 수 있는지 판정한다.

문제

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

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

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

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

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

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

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

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

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