Problem:
 Score : 300 points    Problem Statement In Takahashi Kingdom, there is an archipelago of N islands, called Takahashi Islands.
For convenience, we will call them Island 1 , Island 2 , ..., Island N .  There are M kinds of regular boat services between these islands.
Each service connects two islands. The i -th service connects Island a_i and Island b_i .  Cat Snuke is on Island 1 now, and wants to go to Island N .
However, it turned out that there is no boat service from Island 1 to Island N , so he wants to know whether it is possible to go to Island N by using two boat services.  Help him.      Constraints  3 ≤ N ≤ 200  000  1 ≤ M ≤ 200  000  1 ≤ a_i < b_i ≤ N  (a_i, b_i) \neq (1, N)  If i \neq j , (a_i, b_i) \neq (a_j, b_j) .         Input Input is given from Standard Input in the following format:  N  M  a_1  b_1  a_2  b_2 : a_M  b_M       Output If it is possible to go to Island N by using two boat services, print POSSIBLE ; otherwise, print IMPOSSIBLE .        Sample Input 1 3 2
1 2
2 3      Sample Output 1 POSSIBLE       Sample Input 2 4 3
1 2
2 3
3 4      Sample Output 2 IMPOSSIBLE  You have to use three boat services to get to Island 4 .       Sample Input 3 100000 1
1 99999      Sample Output 3 IMPOSSIBLE       Sample Input 4 5 5
1 3
4 5
2 3
2 4
1 4      Sample Output 4 POSSIBLE  You can get to Island 5 by using two boat services: Island 1 -> Island 4 -> Island 5 .

Solution (Python):


from collections import deque


class EndLoop(Exception):
    pass


def solve():
    while 1:
        try:
            N, M = list(map(int, input().split(" ")))
            Deque1 = deque()
            DequeN = deque()
            edges_1 = [False] * N
            edges_N = [False] * N
            Deque1.extend(edges_1)
            DequeN.extend(edges_N)

            for _ in range(M):
                a, b = list(map(int, input().split(" ")))
                if a == 1:
                    Deque1[b - 1] = True
                elif b == 1:
                    Deque1[a - 1] = True
                elif a == N:
                    DequeN[b - 1] = True
                elif b == N:
                    DequeN[a - 1] = True
                else:
                    pass

            for i in range(N):
                if Deque1[i] == True and DequeN[i] == True:
                    print("POSSIBLE")
                    raise EndLoop

            print("IMPOSSIBLE")
            break
        except:
            break


solve()

Solution (Python):
N, M = [int(n) for n in input().split()]
check = [0] * N
for m in range(M):
  a, b = [int(n) - 1 for n in input().split()]
  if a == 0:
    check[b] += 1
  if b == N-1:
    check[a] += 1
flag = False
for n in range(N):
  if check[n] == 2:
    flag = True

if flag == True:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Solution (Python):

from sys import stdin
input = stdin.readline

N , M = map(int,input().split())
start_input = set()
goal_input = set()

for _ in range(M):
    x , y = map(int,input().split())
    if x == 1:
        start_input.add(y)
    elif y == N:
        goal_input.add(x)
    
if start_input & goal_input:
    print("POSSIBLE")
else :
    print("IMPOSSIBLE")

Solution (Python):
import sys

def possible():
    print("POSSIBLE")
    sys.exit()

def main():
    N, M = map(int, input().split())
    hashdict = dict()
    for i in range(1009):
        hashdict[i] = list()
    alist = list()
    for i in range(M):
        a, b = map(int, input().split())
        if a == 1:
            temp = b % 1009
            hashdict[temp].append(b)
        if b == N:
            alist.append(a)

    for start in alist:
        temp = start % 1009
        if start in hashdict[temp]:
            possible()
    print("IMPOSSIBLE")

if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin
input = stdin.readline

to_middle = set()           
from_middle = set()         
N, M = map(int, (input().split()))
for _ in range(M):
    f, t = map(int, (input().split()))
    if f == 1:
        to_middle.add(t)
    elif t == N:
        from_middle.add(f)

if to_middle & from_middle:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
to_middle = set()           
from_middle = set()         
N, M = map(int, (input().split()))
for _ in range(M):
    f, t = map(int, (input().split()))
    if f == 1:
        to_middle.add(t)
    elif t == N:
        from_middle.add(f)

if to_middle & from_middle:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
to_middle = set()           
from_middle = set()         
N, M = map(int, input().split())
for _ in range(M):
    f, t = map(int, input().split())
    if f == 1:
        to_middle.add(t)
    elif t == N:
        from_middle.add(f)

if to_middle & from_middle:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):

"""
http://abc068.contest.atcoder.jp/tasks/arc079_a
AC
"""

def solve(routes, N):
    result = 'IMPOSSIBLE'
    to_middle = set()           
    from_middle = set()         
    for f, t in routes:
        if f == 1:
            to_middle.add(t)
        elif t == N:
            from_middle.add(f)

    if to_middle & from_middle:
        result = 'POSSIBLE'
    return result



def main():
    N, M = map(int, input().split())
    routes = []
    for _ in range(M):
        routes.append([int(x) for x in input().split()])
    result = solve(routes, N)
    print(result)


if __name__ == '__main__':
    

    to_middle = set()           
    from_middle = set()         
    N, M = map(int, input().split())
    for _ in range(M):
        f, t = map(int, input().split())
        if f == 1:
            to_middle.add(t)
        elif t == N:
            from_middle.add(f)

    if to_middle & from_middle:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

Solution (Python):

"""
http://abc068.contest.atcoder.jp/tasks/arc079_a

"""

def solve(routes, N):
    result = 'IMPOSSIBLE'
    to_middle = set()           
    from_middle = set()         
    for f, t in routes:
        if f == 1:
            to_middle.add(t)
        elif t == N:
            from_middle.add(f)

    if to_middle & from_middle:
        result = 'POSSIBLE'
    return result



def main():
    N, M = map(int, input().split())
    routes = []
    for _ in range(M):
        routes.append([int(x) for x in input().split()])
    result = solve(routes, N)
    print(result)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
from itertools import product, groupby
from math import pi
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = 10 ** 10


def main():
    N, M = map(int, input().split())
    graph = defaultdict(list)
    for _ in range(M):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    for a in graph[1]:
        if N in graph.get(a, []):
            print("POSSIBLE")
            return
    print("IMPOSSIBLE")


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict

d = defaultdict(list)
goal, n = map(int, input().split())
for _ in range(n):
  f, t = map(int, input().split())
  d[f].append(t)
  d[t].append(f)
for current in d[1]:
  if goal in d[current]:
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

Solution (Python):
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]

a = [0] * n

for i in range(m):
    if ab[i][0] == 1:
        a[ab[i][1]] += 1
    if ab[i][1] == n:
        a[ab[i][0]] += 1

if max(a) == 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
n,m=map(int,input().split())
cnt=0
s=[]
kkk=[]
lll=[]
mmm=[]
nnn=[]
while cnt<m:
    num=list(map(int,input().split()))
    s+=num
    cnt+=1
for x in range(m*2):
    if s[x]==n:
        if x%2==0:
            kkk+=[x+1]
        else:
            kkk+=[x-1]
for x in range(len(kkk)):
        lll+=[s[kkk[x]]]
for x in range(m*2):
    if s[x]==1:
        if x%2==0:
            mmm+=[x+1]
        else:
            mmm+=[x-1]
for x in range(len(mmm)):
        nnn+=[s[mmm[x]]]
if len(list(set(lll)&set(nnn)))>0:
    ans="POSSIBLE"
else:
    ans="IMPOSSIBLE"
print(ans)

Solution (Python):
N, M = map(int, input().split())

nxt = set()
prv = set()
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        nxt.add(b)
    elif b == N:
        prv.add(a)

if nxt & prv:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
N, M = map(int, input().split())
set_a, set_b = set(), set()

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        set_a.add(b)
    if b == N:
        set_b.add(a)

if set_a & set_b:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
import sys
lines = sys.stdin.readlines()
N,M = map(int,(lines[0].split()))
seta,setb = set(),set()
for m in range(1,M+1):
    a,b = map(int,(lines[m].split()))
    if a == 1:
        seta.add(b)
    if b == N:
        setb.add(a)        
if seta & setb:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
import fileinput

input = fileinput.input().readline

N,M = map(int,(input().split()))

seta,setb = set(),set()

for m in range(M):
    a,b = map(int,(input().split()))
    if a == 1:
        seta.add(b)
    if b == N:
        setb.add(a)
        
if seta & setb:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
from sys import stdin
input = stdin.readline

N,M = map(int,(input().split()))

ans = "IMPOSSIBLE"

seta,setb = set(),set()

for m in range(M):
    a,b = map(int,(input().split()))
    if a == 1:
        seta.add(b)
    if b == N:
        setb.add(a)
        
if seta & setb:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
from sys import stdin
input = stdin.readline

N,M = map(int,(input().split()))

ans = "IMPOSSIBLE"

seta,setb = set(),set()
af,bf = [False]*M,[False]*M

for m in range(M):
    a,b = map(int,(input().split()))
    if a-1 == 0:
        af[m] = True
        seta.add(b-1)
    if b-1 == N-1:
        bf[m] = True
        setb.add(a-1)
    if af[m] and bf[m]:
        ans = "POSSIBLE"
        break
    
for a in seta:
    if ans == "POSSIBLE":
        break
    if a in setb:
        ans = "POSSIBLE"
        break

print(ans)

Solution (Python):
from collections import defaultdict

def main():
    n, m = map(int, input().split())

    d = defaultdict(lambda: list())
    for _ in range(m):
        a, b = map(int, input().split())
        d[a].append(b)

    flag = 1
    for i in d[1]:
        if n in d[i]:
            print("POSSIBLE")
            flag = 0
            break

    if flag: print("IMPOSSIBLE")
    

if __name__ == "__main__":
    main()

Solution (Python):
N, M = map(int, input().split())
a=set()
b=set()
for i in range(M):
    k,l=map(int, input().split())
    if k==1:
        a.add(l)
    if l==N:
        b.add(k)
if a&b:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
import copy

N, M = map(int, raw_input().split())
dic = {}

for i in range(M):
    tmp = map(int, raw_input().split())
    if tmp[0] not in dic:
        dic[tmp[0]] = []
        dic[tmp[0]].append(tmp[1])
    else:
        dic[tmp[0]].append(tmp[1])
    if tmp[1] not in dic:
        dic[tmp[1]] = []
        dic[tmp[1]].append(tmp[0])
    else:
        dic[tmp[1]].append(tmp[0])

flag = 0

key1 = copy.deepcopy(dic[1])
for i in key1:
    key2 = copy.deepcopy(dic[i])
    for i in key2:
        if i == N:
            flag = 1

if flag == 1:
    print "POSSIBLE"
else:
    print "IMPOSSIBLE"

Solution (Python):
def main():
    
    N, M = map(int, input().split())
    from1 = set()
    toN = set()
    for i in range(M):
        a, b = map(int, input().split())
        if a == 1:
            from1.add(b)
        if b == N:
            toN.add(a)

    if from1 & toN:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

if __name__ == '__main__':
    main()

Solution (Python):
n, m = map(int, input().split())
s1 = []
s2 = []
for i in range(m):
	a, b = map(int, input().split())
	if a == 1:
		s1.append(b)
	elif b == n:
		s2.append(a)
if len(set(s1) & set(s2)) == 0:
	print("IMPOSSIBLE")
else:
	print("POSSIBLE")

Solution (Python):
a=[]
b={}
n,m=map(int,input().split())
for _ in range(m):
	i,j=map(int,input().split())
	if i==1:
		a.append(j)
	elif j==n:
		b[i]=1
for i in a:
	if i in b:
		print('POSSIBLE')
		break
else:
	print('IMPOSSIBLE')

Solution (Python):
def dfs(i, p):
    if(p == n):
        return 1
    if(i == 2):
        return 0
    ret = 0
    for q in adj[p]:
        ret += dfs(i+1, q)
    return ret

n, m = map(int, input().split())
adj = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)
ans = dfs(0, 1)

print("POSSIBLE" if(ans) else "IMPOSSIBLE")

Solution (Python):
a=[]
b={}
n,m=map(int,input().split())
for _ in range(m):
	i,j=map(int,input().split())
	if i==1:
		a.append(j)
	elif j==n:
		b[i]=1
for i in a:
	if i in b:
		print('POSSIBLE')
		break
else:
	print('IMPOSSIBLE')

Solution (Python):
a=[]
b={}
n,m = map(int,input().split())
for _ in range(m):
	i,j = map(int,input().split())
	if i==1:
		a.append(j)
	elif j==n:
		b[i]=1
for i in a:
	if i in b:
		print('POSSIBLE')
		break
else:
	print('IMPOSSIBLE')

Solution (Python):


n, m = map(int, raw_input().split())
island = [[] for i in range(n+1)]
ans = 'IMPOSSIBLE'
for i in range(m):
    a, b = map(int, raw_input().split())
    island[a].append(b)
    island[b].append(a)
for i in island[1]:
    if(n in island[i]):
        ans = 'POSSIBLE'
        break
print(ans)

Solution (Python):
n,m=map(int,input().split())
r=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    r[a-1].append(b-1)
    r[b-1].append(a-1)
ans=False
for i in range(1,n-1):
    if 0 in r[i]and (n-1) in r[i]:
        ans=True

print("POSSIBLE" if ans else "IMPOSSIBLE")

Solution (Python):
N,M=map(int, input().split())
p=[]
for x in range(M):
    p.append(input())
A=[]
B=[]
for x in range(M):
    a,b=map(int,p[x].split())
    A.append(a)
    B.append(b)
    
isl=[]
for x in range(N):
    isl.append(0)
for x in range(M):
    if A[x]==1:
        isl[B[x]]=1
for x in range(M):
    if B[x]==N:
        isl[A[x]]=isl[A[x]]+1

if 2 in isl:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
import sys

input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    m = set()
    for _ in range(M):
        a, b = map(int, input().split())
        if a < b:
            m.add((a,b))
        else:
            m.add((b,a))
    for i in range(2, N):
        if (1, i) in m and (i, N) in m:
            print("POSSIBLE")
            break
    else:
        print("IMPOSSIBLE")
main()

Solution (Python):
import sys

input = sys.stdin.readline

def main():
    N, M = map(int, input().split(" "))
    m = set()
    for _ in range(M):
        a, b = map(int, input().split(" "))
        if a < b:
            m.add((a,b))
        else:
            m.add((b,a))
    for i in range(2, N):
        if (1, i) in m and (i, N) in m:
            print("POSSIBLE")
            break
    else:
        print("IMPOSSIBLE")
main()

Solution (Python):
import sys

input = sys.stdin.readline

N, M = map(int, input().split(" "))
m = set()

for _ in range(M):
    a, b = map(int, input().split(" "))
    if a < b:
        m.add((a,b))
    else:
        m.add((b,a))


for i in range(2, N):
    if (1, i) in m and (i, N) in m:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Solution (Python):
import sys

input = sys.stdin.readline

N, M = list(map(int, input().split(" ")))
m = set()

for _ in range(M):
    a, b = list(map(int, input().split(" ")))
    if a < b:
        m.add((a,b))
    else:
        m.add((b,a))


for i in range(2, N):
    if (1, i) in m and (i, N) in m:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Solution (Python):
N, M = list(map(int, input().split(" ")))
m = set()

for _ in range(M):
    a, b = list(map(int, input().split(" ")))
    if a < b:
        m.add((a,b))
    else:
        m.add((b,a))


for i in range(2, N):
    if (1, i) in m and (i, N) in m:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Solution (Python):


N, M = map(int, raw_input().split())
start, finish = [], []
for i in range(M):
    a, b = map(int, raw_input().split())
    if a == 1:
        start.append(b)
    elif b == N:
        finish.append(a)

if set(start) & set(finish):
    print 'POSSIBLE'
else:
    print 'IMPOSSIBLE'

Solution (Python):
def Q3(N, M, *arg):
    import numpy as np
    route = np.reshape(np.array(*arg), (M, 2))
    string = 'IMPOSSIBLE'
    p = [False] * N
    q = [False] * N
    for x in route:
        if x[0] == 1:
            p[x[1]] = True
        elif x[1] == N:
            q[x[0]] = True
    for i in range(N):
        if p[i] and q[i]:
            string = 'POSSIBLE'
            break
    return string

N, M = map(int, input().split())
l = [list(map(lambda x: int(x), input().split())) for i in range(M)]
l = [flatten for inner in l for flatten in inner]
print(Q3(N,M,l))

Solution (Python):
n, m = map(int, input().split())
s = [False] * n
g = [False] * n
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        s[b] = True
    if b == n:
        g[a] = True

ans = "IMPOSSIBLE"
for i in range(n):
    if s[i] and g[i]:
        ans = "POSSIBLE"
        break
print(ans)

Solution (Python):
N, M = map(int, input().split())
from1 = [False] * N
toN = [False] * N
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        from1[b] = True
    if b == N:
        toN[a] = True
msg = "IMPOSSIBLE"
for i in range(N):
    if from1[i] and toN[i]:
        msg = "POSSIBLE"
        break
print(msg)

Solution (Python):
N, M = map(int, input().split())
from1 = set()
toN = set()
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        from1.add(b)
    if b == N:
        toN.add(a)
msg = "IMPOSSIBLE" if from1.isdisjoint(toN) else "POSSIBLE"
print(msg)

Solution (Python):
N, M = map(int,input().split())
from1 = set()
toN = set()
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        from1.add(b)
    if b == N:
        toN.add(a)
if from1 & toN :
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split())
graph = [list() for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    
for g1 in graph[0]:
    if N-1 in graph[g1]:
        print("POSSIBLE")
        break
        
else:
    print("IMPOSSIBLE")

Solution (Python):


import math

N, M = map(int, input().split())
start = [False] * N
goal = [False] * N
for i in range(M):
    a1, a2 = map(int, input().split())
    if (a1 == 1):
        start[a2 - 1] = True
    if (a2 == N):
        goal[a1 - 1] = True

def check():
    for i in range(N):
        if (start[i] & goal[i]):
            return('POSSIBLE')
    return('IMPOSSIBLE')

print(check())

Solution (Python):
N, M = map(int,raw_input().split())
S = []
for i in range(M):
        S.append(map(int, raw_input().split()))

toN =[]
first = []
end = False

for i in range(M):
    if S[i][1] == N:
        toN.append(S[i][0])

for i in range(M):
    if S[i][0] == 1:
        first.append(S[i][1])

toN = set(toN)
first = set(first)

if toN.intersection(first):
    print "POSSIBLE"

else:
    print "IMPOSSIBLE"

Solution (Python):
N, M = map(int, raw_input().split())
G = {v: set() for v in range(N+1)}
for i in range(M):
    a, b = map(int, raw_input().split())
    G[a].add(b)
    G[b].add(a)
ok = False
for v in range(N+1):
    if (1 in G[v]) and (N in G[v]):
        ok = True
        break
print "POSSIBLE" if ok else "IMPOSSIBLE"

Solution (Python):
n,m=map(int,input().split())
arr1=set()
arrn=set()
for _ in range(m):
    a,b=map(int,input().split())
    if a==1 and b==n or a==n and b==1:
        print("POSSIBLE")
        exit(0)
    else:
        if a==1:
            arr1.add(b)
        elif a==n:
            arrn.add(b)
        elif b==1:
            arr1.add(a)
        elif b==n:
            arrn.add(a)
if len(arr1.intersection(arrn))>0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):


(n, m) = map(int, input().split())
begin_to = set()
end_from = set()
for i in range(m):
    (a, b) = map(int, input().split())
    if a == 1:
        begin_to.add(b)
    if b == n:
        end_from.add(a)

if begin_to.isdisjoint(end_from):
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Solution (Python):
N, M = list(map(int, input().split()))
start = set([])
end = set([])
for i in range(M):
    a, b = list(map(int, input().split()))
    if a == 1 or b == 1:
        start.add(a*b)
    if a == N or b == N:
        end.add(a * b / N)
flag = 0
for i in start:
    if i in end:
        print("POSSIBLE")
        flag = 1
        break
if not(flag):
    print("IMPOSSIBLE")

Solution (Python):

class Scanner(object):
    """docstring for Scanner."""
    s = []
    idx = 0
    separater = ""

    def __init__(self, separater=" "):
        self.separater = separater

    def next(self):
        while self.idx >= len(self.s):
            st = input()
            while st == "":
                st = input()
            self.s = st.split(self.separater)
            self.idx = 0
        self.idx += 1
        return self.s[self.idx - 1]

    def next_int(self):
        return int(self.next())

    def next_float(self):
        return float(self.next())


sc = Scanner()
N = sc.next_int()
M = sc.next_int()
graph = []
for i in range(N):
    graph.append([])
for i in range(M):
    a = sc.next_int() - 1
    b = sc.next_int() - 1

    graph[a].append(b)
    graph[b].append(a)
successed = False

for neighbors in graph[N - 1]:
    for neighbor in graph[neighbors]:
        if neighbor == 0:
            successed = True

if successed:
    print("POSSIBLE")

else:
    print("IMPOSSIBLE")

Solution (Python):
from sets import Set

def solve():
	n, m = map(int, raw_input().split())
	to1 = Set()
	toN = Set()

	for i in range(m):
		x, y = map(int, raw_input().split())
		if x == 1:
			to1.add(y)
		if x == n:
			toN.add(y)
		if y == 1:
			to1.add(x)
		if y == n:
			toN.add(x)

	for i in range(n):
		if i in to1 and i in toN:
			print "POSSIBLE"
			return
			
	print "IMPOSSIBLE"

solve()

Solution (Python):
def solve(n, m, a, b):
    islands = set()

    for i in range(m):
        if(a[i] == 1):
            islands.add(b[i])
        if(b[i] == 1):
            islands.add(a[i])

    for i in range(m):
        if(a[i] == n and b[i] in islands):
            return "POSSIBLE"
        if(b[i] == n and a[i] in islands):
            return "POSSIBLE"
    return "IMPOSSIBLE"

(n, m) = map(int, input().split())
a = []
b = []

for i in range(m):
    (ai, bi) = map(int, input().split())
    a.append(ai)
    b.append(bi)

print(solve(n, m, a, b))

Solution (Python):
import sys

N, M = map(int, input().split())
a = []
b = []

for i in range(M):
    c, d = map(int, input().split())
    a.append(c)
    b.append(d)

s = set()

for i in range(M):
    if b[i] == N:
        s.add(a[i])

for i in range(M):
    if a[i] == 1 and b[i] in s:
        print('POSSIBLE')
        sys.exit()

print('IMPOSSIBLE')

Solution (Python):



import sys
from collections import defaultdict

inputs = list(map(int, sys.stdin.readline().split()))

n = inputs[0]
m = inputs[1]

ai = defaultdict(list)

for i in range(m):
	inputs = list(map(int, sys.stdin.readline().split()))
	a = inputs[0]
	b = inputs[1]
	ai[a].append(b)
	ai[b].append(a)


pos = 1

for dst in ai[pos]:
	if dst == n:
		print("POSSIBLE")
		sys.exit()

	for dst2 in ai[dst]:
		if dst2 == n:
			print("POSSIBLE")
			sys.exit()

print("IMPOSSIBLE")

Solution (Python):


c1 = []
c2 = []
q = input().split()
n = [input().split() for i in range(int(q[1]))]
 
for m in n:
  if m[0] == "1":
    c1.append(m[1])
  if m[1] == q[0]:
    c2.append(m[0])
if set(c1) & set(c2):
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Solution (Python):
N,M=map(int,input().split())
start=[]
end=[]
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        start.append(b)
    elif b==N:
        end.append(a)

startset=set(start)
endset=set(end)
if startset & endset:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
n,m=map(int,input().split(" "))
l=[]
bone=[]
for i in range(m):
		a,b=input().split(" ")
		if a=="1":l.append(b)
		if b==str(n):bone.append(a)

ans=list(set(l) & set(bone))
if len(ans)!=0:
	print("POSSIBLE")
else:			
	print("IMPOSSIBLE")

Solution (Python):
n,m = map(int, raw_input().split())
s = set()
t = set()
for _ in range(m):
    a,b = map(int, raw_input().split())
    if a == 1:
        s.add(b)
    elif b == 1:
        s.add(a)
    if a == n:
        t.add(b)
    elif b == n:
        t.add(a)
u = s.intersection(t)
if len(u) == 0:
    print 'IMPOSSIBLE'
else:
    print 'POSSIBLE'

Solution (Python):



def main():
    n, m = map(int, raw_input().split())

    s = [0] * 200010
    t = [0] * 200010
    for _ in xrange(m):
        a, b = map(int, raw_input().split())
        if a == 1:
            s[b] = True
        if b == n:
            t[a] = True

    for i in xrange(1, n+1):
        if s[i] and t[i]:
            print "POSSIBLE"
            return

    print "IMPOSSIBLE"

main()

Solution (Python):
from collections import deque
N, M = map(int, raw_input().split(' '))
route = [map(int, raw_input().split(' ')) for _ in xrange(M)]

A = {}
for a, b in route:
    A.setdefault(a, []).append(b)
    A.setdefault(b, []).append(a)


def bfs(A, start, end):
    visited = set()
    queue = deque()
    visited.add(start)
    queue.append((start, 0))
    while len(queue) > 0:
        a, d = queue.popleft()
        if d >= 2:
            break
        for b in A[a]:
            if b == end:
                return True
            if b not in visited:
                visited.add(b)
                queue.append((b, d+1))
    return False


if bfs(A, 1, N):
    print 'POSSIBLE'
else:
    print 'IMPOSSIBLE'

Solution (Python):
N,M=[int(x) for x in input().split()]
set1=[]
setn=[]
for i in [None]*M:
    ipt=[int(x) for x in input().split()]
    if 1 in ipt:
        set1 += ipt
    if N in ipt:
        setn += ipt
if set(set1) & set(setn):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
import sys 

N,M  = map(int,input().split())
     
a = [[0 for i in range(2)] for j in range(M)]
b = [] 
c = []

for i in range(M):
  a[i][0] , a[i][1] = map(int,input().split())
  first, second = a[i][0],a[i][1]
  if first == 1:
    b.append(second)
  if second == N:
    c.append(first)

b_set = set(b)
c_set = set(c)

if list(b_set & c_set) is None or len(list(b_set & c_set)):
  res = ('POSSIBLE')
else:
  res = ('IMPOSSIBLE')

print(res)

Solution (Python):
import sys
from collections import Counter





def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def solve():
    n, m = read_int_list()
    c = Counter()
    for i in range(m):
        a, b = read_int_list()
        if a == 1:
            c[b] += 1
        if b == n:
            c[a] += 1

    if 2 in c.values():
        return 'POSSIBLE'
    return 'IMPOSSIBLE'


res = solve()
print(res)

Solution (Python):


N, M = tuple(map(int, input().split()))

graph = [ [] for i in range(N+1)]
for i in range(M):
    a, b = tuple(map(int, input().split()))
    graph[a].append(b)
    graph[b].append(a)

res = "IMPOSSIBLE"
for i in range(2, N):
    if 1 in graph[i] and N in graph[i]:
        res = "POSSIBLE"

print(res)

Solution (Python):
import sys
from collections import Counter




def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


n, m = read_int_list()
c = Counter()

for i in range(m):
    a, b = read_int_list()
    if a == 1:
        c[b] += 1
    if b == n:
        c[a] += 1

res = 'IMPOSSIBLE'
if 2 in c.values():
    res = 'POSSIBLE'
print(res)

Solution (Python):
n, m = map(int, input().split())
des= [0]*(n+1)
a = 1
for i in range(0, m):
	b = (list(map(int, input().split())))
	if b[0] == 1:
		des[b[1]] += 1
		if des[b[1]] == 2:
			print('POSSIBLE')
			a = 0
			break
	if b[1] == n:
		des[b[0]] += 1
		if des[b[0]] == 2:
			print('POSSIBLE')
			a = 0
			break
		
if a:
	print('IMPOSSIBLE')

Solution (Python):
import sys

input = sys.stdin.readline

a = list(map((int), input().split(' ')))
N, M = a[0], a[1]
 
first = []
second = []
 
for i in range(M):
    
    b = list(map((int),input().split(' ')))
    start, end = b[0], b[1]
    
    if start == 1:
        first.append(end)
    if end == N:
        second.append(start)
        
first_set = set(first)
second_set = set(second)
 
matched_l = list(first_set & second_set)
 
if matched_l is None or len(matched_l) == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Solution (Python):
import sys
 
input = sys.stdin.readline

a=input()
b=a.split(" ")
N=int(b[0])
M=int(b[1])
in2=[]
out2=[]
for i in range(M):
    c=input()
    d=c.split(" ")
    in1=int(d[0])
    out=int(d[1])
    if in1==1:
        in2.append(str(out))
    elif out==N:
        out2.append(str(in1))
        
in2_set=set(in2)
out2_set=set(out2)
matched_list=list(in2_set & out2_set)

if len(matched_list)==0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Solution (Python):



a = list(map((int), input().split(' ')))
N, M = a[0], a[1]

first = []
second = []

for i in range(M):
    
    b = list(map((int),input().split(' ')))
    start, end = b[0], b[1]
    
    if start == 1:
        first.append(end)
    if end == N:
        second.append(start)
        
first_set = set(first)
second_set = set(second)

matched_l = list(first_set & second_set)

if matched_l is None or len(matched_l) == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Solution (Python):
a=input()
b=a.split(" ")
N=int(b[0])
M=int(b[1])
in2=[]
out2=[]
for i in range(M):
    c=input()
    d=c.split(" ")
    in1=int(d[0])
    out=int(d[1])
    if in1==1:
        in2.append(str(out))
    elif out==N:
        out2.append(str(in1))
        
in2_set=set(in2)
out2_set=set(out2)
matched_list=list(in2_set & out2_set)

if len(matched_list)==0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Solution (Python):
N,M = map(int,input().split())
origindestination = {}

for i in range(1,N+1):
    origindestination[i] = []
    
for i in range(M):
    a,b = map(int,input().split())
    origindestination[a].append(b)

for destination in origindestination[1]:
    if N in origindestination[destination]:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Solution (Python):
N,M=[int(i) for i in input().split()]
a=[]
b=[]
c=[]
for i in range(M):
    x,y=[int(i) for i in input().split()]
    if x==1 :
        c.append(y)
    if y==N:
        c.append(x)
if len(c)==len(set(c)):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Solution (Python):
N, M = map(int, input().split())
a = [0] * M
b = [0] * M

for i in range(M):
    a[i], b[i] = map(int, input().split())

s = []
t = []

for i in range(M):
    if a[i] == 1:
        s.append(b[i])
    elif b[i] == N:
        t.append(a[i])

if len(set(s) & set(t)) == 0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Solution (Python):
N,M=map(int,input().split())
island=[[] for i in range(N)]
for j in range(M):
    c,d=map(int,input().split())
    island[d-1].append(c)
    island[c-1].append(d)
f = 0
for k in range(N):
    if 1 in island[k]:
        if N in island[k]:
            f += 1
            break
        else:
            pass
    else:
        pass
if f>0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')