성재와 민혁이가 달리기 시합을 한다.

먼저 시합의 주선자인 서연이가 N개의 지역 중 몇 곳의 지역을 골라서

원형(출발 지점과 도착 지점이 같은) 트랙을 정한 후 둘이서 한 바퀴 돈다.

서연이는 둘의 기록을 재고 승자를 결정한다. (당연히 완주시간이 짧은 쪽이 승자가 된다)

민혁이가 성재를 항상 이겨왔던 것을 지겨워하는 서연이는 성재가 완승하는 트랙을 만들고 싶어한다.

한편, 서연이는 성재와 민혁이의 달리기 기록을 알고 있는 길을 M개 알고 있다.

민혁이가 이길 가능성을 아예 없애기 위해선 M개의 길들만으로 트랙을 만들어야 한다.

한편, 경유 지역이 너무 많으면 주선자인 자신이 헷갈리기 때문에 경유 지역의 수는 최소화해야 한다.

서연이를 도와 성재가 완승하는 트랙을 구하는 프로그램을 작성하여라.

[서브태스크]

서브태스크 1 : N ≤ 11

서브태스크 2 : N ≤ 22

서브태스크 3 : N ≤ 111

서브태스크 4 : N ≤ 222

서브태스크 5 : 추가 제약 없음

달리기 timer 2초 memory 128MB

달리기 2초 128MB