IOI 2012 day1 2- 낙하산 고리들(Parachute rings) > 문제은행 : 정보올림피아드&알고리즘




2621 : 낙하산 고리들(Parachute rings)

제한시간
5000 ms   
메모리제한
64 MB   
해결횟수
0 회   
시도횟수
3 회   

문제

레오나르도 다 빈치의 코덱스 아틀란티쿠스 에는 최초로 설계한 꽤 정교한 낙하산이 설명되어 있는데, 

이 다 빈치의 낙하산은 피라미드 모양의 나무 구조를 통해 열리는 우산모양의 리넨 옷감으로 설계되어있다.

 

고리 구조

스카이다이버 아드리안 니콜라스는 500년 이상 오래된 다 빈치의 디자인을 시험해보았다. 

이를 위해, 사람의 몸을 다 빈치의 낙하산에 묶기 위한 최신식 초경량 구조를 사용하였다.

우리는 리넨 옷감에도 걸 수 있는 고리 구조를 사용하고자 한다. 각각의 고리는 유연하고 강한 소재로 만들어졌다. 

모든 고리들은 열고 닫을 수 있으므로, 다른 고리들과 쉽게 연결될 수 있다. 체인은 고리 구조의 특별한 형태를 말한다. 

아래에 있는 그림처럼, 각각의 고리들이 (최대 두 개의) 인접한 고리들과 차례대로 연결되어 있고, 

시작과 끝이 있는 고리 구조는 체인이 된다. (시작과 끝에 있는 고리들은 각각 최대 하나의 다른 고리들과 연결된다.)


특히, 고리 하나도 마찬가지로 체인이다.



 

하나의 고리가 세 개 이상의 다른 고리들과 연결된 고리 구조의 형태도 당연히 가능하다. 

이러한 고리 구조에서, 어떤 하나의 고리를 열어서 없앤 후에 남은 다른 고리들이 모두 체인의 형태를 만들 때 (혹은 고리가 하나도 남지 않았을 때), 

그 고리를 중요한 고리라고 한다. 다시 말해, 중요한 고리를 제거하면, 체인만 남게 된다.


예제

다음의 그림과 같이, 0번부터 6번까지 번호가 매겨진 7개의 고리를 생각해보자.

이 고리 구조에는 2개의 중요한 고리가 있다. 

그 중 하나는 2번인데, 이 고리를 없애면 남은 고리들이 [1], [0, 5, 3, 4], 그리고 [6]의 체인이 된다. 

다른 하나는 3번인데, 이 고리를 없애면 남은 고리들이 [1, 2, 0, 5], [4], 그리고 [6]의 체인이 된다. 

만약 그 이외의 다른 고리들을 없애면, 체인이 아닌 것이 남아있게 된다. 

예를 들어, 5번 고리를 없애면 [6]은 체인이 되지만, 0번, 1번, 2번, 3번, 그리고 4번 고리로 만들어진 고리 구조는 체인이 아니다.

 


 

해야할 일

여러분이 할 일은 입력으로 주어지는 고리 구조에서, 중요한 고리의 개수를 출력하는 프로그램을 작성하는 것이다.

 

 


입력형식

 

입력의 첫줄에 고리의 개수 N(1≤N≤1,000,000)과, 만들 고리의 구조 개수 L(1≤L≤1,000,000)이 주어진다.
다음줄부터 L줄에 2개의 정수 A,B 또는 -1이 주어진다. A와 B인 경우는 A번 고리와 B번 고리를 서로 연결함을 의미고, -1은 현재의 고리구조 형태에서 중요한 고리의 개수를 출력하라는 의미이다. 
N개의 고리가 있을 때 0부터 N-1까지 번호가 붙는다.

 


출력형식

입력에서 -1이 주어지면 그때의 고리구조의 형태에서 중요한 고리의 개수를 한줄에 하나씩 출력한다.


입력 예

7 8
1 2
0 5
-1
2 0
3 2
3 5
4 3
-1

출력 예

7
2


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP