범수는 올해 크리스마스도 여전히 혼자 놀 것을 예상하고 미리 크리스마스 준비에 착수했다. 왜 벌써부터 준비하냐고 묻는다면 친구가 없어서 시간이 많다. 어쨋든 그는 크리스마스 트리를 장식하기 위하여 조금 특이한 전구를 만들어 그것들을 연결하여 트리를 장식하려는 계획을 세우고 있다.

범수가 만드는 전구는 다음과 같은 특징이 있다.

● 전구는 항상 하나의 전원으로부터만 전력을 공급받을 수 있다.

● 전구 자체가 다른 전구의 전원으로써 전력을 공급해주는 것이 가능하다.

● 전원이 되는 전구는 자신에게 전원이 공급되면 자신에게 연결된 전구에게도 반드시 전원을 공급해주어야 한다.

여기까지만 했어도 좋을텐데 . . .

범수는 그래도 크리스마스까지 시간이 많이 남기 때문에 여기에 몇 가지를 손봐서 이러한 특징을 가지면서 약간 다른 2 종류의 전구를 만들었다.

● type 1의 전구는 자신이 다른 전구의 전원이 될 때 연결된 전구 중에 하나의 전구에만 전원을 공급한다.

● type 2의 전구는 자신이 다른 전구의 전원이 될 때 연결된 전구 모두에게 전원을 공급한다.

범수는 이러한 전구들을 연결하여 연결된 형태에 따라서 켜지는 전구의 형태가 다른 장식을 만들려고 한다. 그리고 그렇게 만든 전구 중에서 k번째 전구는 반드시 켜고 싶다. 하지만 전구가 동작하는 것이 생각보다 복잡하게 되자 범수는 전구들을 연결했을 때 어떻게 동작할지 예측하기가 힘들어졌다. (왜 복잡하게 만들었냐하면 그는 시간이 많다.) 어차피 방에서 혼자 보낼 크리스마스인데 무슨 고민을 하느냐고 생각할 수 있지만 가엾은 그를 위해서 전구가 어떻게 동작할지 출력해주는 프로그램을 작성해주자.

마지막으로 범수가 연결한 전구들의 특성은 다음과 같다.

● 자기 자신으로 연결되는 전구는 없다.

● 전원은 1번 전구에서부터 공급된다.

● 모든 전구는 연결되어 있고 1번 전구로부터 임의의 전구까지 연결되어 있는 경로는 유일하다.

● type 1의 전구에 전력이 공급될 때 연결된 전구들 중에 특별히 켜져야 될 전구가 없다면 연결된 전구 중에서 가장 낮은 번호의 전구에 전원을 공급한다.

● 위의 특성들을 만족할 때 k번째 전구가 켜졌을 때 같이 켜지는 전구들은 유일하다.

#2457 upload 3 done 3 how_to_reg 3

전구 timer 1s memory - MB

#2457

전구 1s - MB