====== 불꽃놀이의 아름다움 2 ======

===== 풀이 =====
  * 풀이는 [[https://github.com/ssu-sccc/2025scon/blob/main/editorial-slide.pdf|에디토리얼]] 참고
  * 그래프가 단순사이클을 한개만 갖고 있는 형태라는 것을 눈치채면, 답은 최대 3이라는 것을 알수 있으므로, 2-colorable 인지만 확인하면 된다. 시간복잡도는 O(V+E)이므로 O(N)이다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 33915. 불꽃놀이의 아름다움 2".

- Problem link: https://www.acmicpc.net/problem/33915
- Solution link: http://www.teferi.net/ps/problems/boj/33915

Tags: [bi-coloring]
"""

import sys
from teflib import graph as tgraph


def main():
    N = int(sys.stdin.readline()) 
    graph = tgraph.create_graph_from_input(N, N)
    print('2' if tgraph.is_bipartite(graph) else '3')


if __name__ == '__main__':
    main()

</dkpr>
  * Dependency: [[:ps:teflib:graph#is_bipartite|teflib.graph.is_bipartite]]

{{tag>BOJ ps:problems:boj:골드_4}}