BASIN CITY 감시

BASIN CITY는 범죄율이 매우 높다. 경찰은 치안을 강화하기로 하고, 신호를 위반하는 차를 감시할 교통 드론을 교차로에 설치하려 한다. 어떤 차가 빨간불에 지나가면 그 교차로의 드론이 차를 쫓아가 세우고 운전자에게 딱지를 발부한다.

드론은 성능이 좋지 않다. 추격 중에도 다음 교차로에 닿기 전에 멈춘다. 그보다 멀리 가면 자기 집, 곧 자신이 배치된 신호등으로 돌아오는 길을 잃기 때문이다. 게다가 드론은 다른 드론을 감지하지 못한다. 그래서 경찰 연구소는 어떤 교차로에 드론을 두면 그 교차로와 도로로 이어진 교차로에는 드론을 두지 않는 편이 좋다는 결론을 내렸다. 다른 여러 도시와 마찬가지로 BASIN CITY에는 이웃한 교차로가 4개를 넘는 교차로가 없다.

드론 값은 정부가 대므로 경찰은 허용되는 만큼 많이 사려고 한다. 드론 개수 $k$가 주어질 때, 드론이 놓인 두 교차로가 서로 이웃하지 않도록 드론을 정확히 $k$대 배치할 수 있는지 판정하라.

첫째 줄에 배치할 드론의 개수 $k$가 주어진다 ($0 \le k \le 15$). 둘째 줄에 BASIN CITY의 교차로 개수 $n$이 주어진다 ($1 \le n \le 100\,000$). 이어지는 $n$개의 줄에 교차로의 정보가 순서대로 주어진다. $i$번째 줄은 정수 $d$로 시작하는데, $d$는 $i$번 교차로와 이웃한 교차로의 개수다 ($0 \le d \le 4$). 그 뒤에 이웃한 교차로의 번호 $d$개가 주어진다. 이 번호는 서로 다르고 $i$와도 다르다. 교차로에는 1번부터 $n$번까지 번호가 붙어 있다.

이웃한 두 교차로에 드론이 함께 놓이는 일 없이 드론 $k$대를 배치할 수 있으면 첫째 줄에 possible을 출력한다. 그렇지 않으면 impossible을 출력한다.