====== 색칠하기 ======

===== 풀이 =====
  * 기본적인 [[ps:tutorial:이분 그래프]] 판별 문제. 2색으로 색칠이 가능한 그래프 == 이분 그래프이다
  * 시간복잡도는 O(V+E)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 13265. 색칠하기".

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

Tags: [graph]
"""

from teflib import psutils
from teflib import graph as tgraph


@psutils.run_n_times
def main():
    _n, _m, graph = tgraph.from_input()
    print('possible' if tgraph.is_bipartite(graph) else 'impossible')


if __name__ == '__main__':
    main()

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

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