107AC - ABC068C: Cat Snuke and a Voyage

ABC068-C (300 points)

問題

個の頂点と 本の枝からなるグラフが与えられたときに, 頂点 から頂点 に距離 で到達可能か判定する.
ただし頂点 間に枝はないものとする.

• 
• 

方針

• 頂点 から距離 の頂点, 頂点 から距離 の頂点をそれぞれ列挙.
• それぞれの集合に共通部分＝経由点があればPOSSIBLE, なければIMPOSSIBLE.

import math

# input
N, M = map(int, input().split())
edge_lst = [list(map(int, input().split())) for _ in range(M)]

d_1 = [] # 頂点1から距離1の頂点
d_N = [] # 頂点Nから距離1の頂点

for e in edge_lst:
    if e[0] == 1:
        d_1.append(e[1])
    if e[1] == N:
        d_N.append(e[0])

ans = list(set(d_1) & set(d_N))

if len(ans) == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')