시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 60 11 6 27.273%

문제

N개의 정점과 M개의 간선으로 이루어져 있는 무방향 그래프가 있다.

이 때, 그래프에서 간선을 일부 지워서 모든 정점의 차수를 1로 만들 수 있는지 없는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M (2 ≤ N ≤ 100, 1 ≤ M ≤ 100)이 주어진다.

둘째 줄부터 M개의 줄에 간선의 정보가 주어진다.

그래프의 두 정점을 연결하는 간선이 여러개일 수도 있다. 루프는 존재하지 않는다. 정점 번호는 1부터 시작한다.

출력

그래프에서 간선을 일부 지워서 모든 정점의 차수를 1로 만들 수 있으면 1을, 없으면 0을 출력한다.

예제 입력

2 2
1 2
1 2

예제 출력

1

예제 입력 2

3 2
1 2
2 3

예제 출력 2

0

예제 입력 3

4 6
1 2
1 3
1 4
2 3
2 4
3 4

예제 출력 3

1

힌트

출처

  • 데이터를 추가한 사람: doju
  • 문제의 오타를 찾은 사람: vjerksen